D
DevExCode

LeetCode 2375: Construct Smallest Number From DI String Solution

Master LeetCode problem 2375 (Construct Smallest Number From DI String), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

2375. Construct Smallest Number From DI String

Medium
StringBacktrackingStackGreedy

Problem Explanation

Explanation

To construct the smallest number from a DI string, we can use a greedy approach. We iterate through the given pattern and for each 'I', we place the smallest available digit, and for each 'D', we place the largest available digit.

  1. Initialize an array result with numbers from 1 to n+1.
  2. Iterate through the pattern:
    • If the current character is 'I', leave the smallest available number and move to the next.
    • If the current character is 'D', replace the current number with the largest available number and decrease it.
  3. Return the resulting array as a string.

The time complexity of this approach is O(n) where n is the length of the pattern since we iterate through the pattern only once. The space complexity is O(n) to store the resulting array.

Solution Code

class Solution {
    public String constructSmallestNumber(String pattern) {
        int n = pattern.length();
        int[] result = new int[n + 1];
        int start = 1, end = n + 2;
        
        for (int i = 0; i < n; i++) {
            if (pattern.charAt(i) == 'I') {
                result[i] = start++;
            } else {
                result[i] = end--;
            }
        }
        
        result[n] = start;
        
        StringBuilder sb = new StringBuilder();
        for (int num : result) {
            sb.append(num);
        }
        
        return sb.toString();
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 2375 (Construct Smallest Number From DI String)?

This page provides optimized solutions for LeetCode problem 2375 (Construct Smallest Number From DI String) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 2375 (Construct Smallest Number From DI String)?

The time complexity for LeetCode 2375 (Construct Smallest Number From DI String) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2375 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2375 in Java, C++, or Python.

Back to LeetCode Solutions