Construct Smallest Number From DI String

Leetcode Problem:

• Construct Smallest Number From DI String

Summary

• Find the lexicographically smallest possible string num that meets the conditions given a 0-indexed string pattern of length n consisting of the characters 'I' meaning increasing and 'D' meaning decreasing.

Approach

• The approach used is to first initialize a character array num with the digits from 1 to 9
• Then, for each character in the pattern, if the character is 'I', we shift all the digits to the right to maintain the increasing order
• If the character is 'D', we shift all the digits to the left to maintain the decreasing order
• Finally, we construct the string num by concatenating the digits in the array.

Complexity

• O(n), where n is the length of the pattern string.

Explanation

• The provided solution code uses a character array num to store the digits from 1 to 9
• It then iterates over the pattern string, shifting the digits in the array as needed to maintain the increasing or decreasing order
• Finally, it constructs the string num by concatenating the digits in the array
• The time complexity is O(n) because it needs to iterate over the pattern string once
• The space complexity is also O(n) because it needs to store the digits in the array.

Solution Code:

class Solution {
public:
    string smallestNumber(string pattern) {
        char num[10] = {0};
        num[0] = '1';
        for(int i = 1; i <= pattern.size(); i++ ){
            num[i] = '1'+i;
            int j = i;
            while(j > 0 && pattern[j-1] == 'D'){
                char t = num[j];
                num[j] = num[j-1];
                num[j-1] = t;
                j--;
            }
        }
        string ans = "";
        ans += num[0];
        for(int i = 1; i <= pattern.size(); i++){
            ans += num[i];
        }
        return ans;
    }
};