LeetCode 2375: Construct Smallest Number From DI String

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.

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();
    }
}