10. Number following a pattern

The problem can be found at the following link: Question Link

My Approach

To generate the minimum number following a given pattern,

• I iterate through the input string S and create a vector of pairs to store consecutive characters and their counts.

• Then, I construct the output string based on this information.

• The key idea is to increment or decrement the numbers in the output string based on whether the corresponding character in the input is I or D.

  • After observing some pattern I found that when decrementing, we need to include count + 1 in our output, and when incrementing, we should use count - 1 characters in the output.

Time and Auxiliary Space Complexity

• Time Complexity: O(N), where N is the length of the input string.

• Auxiliary Space Complexity: O(N), for storing the pairs representing consecutive characters and their counts.

Code (C++)

class Solution{   
public:
    string printMinNumberForPattern(string S){
        vector<pair<char, int>> col;
        char curr = S[0];
        int c = (S[0] == 'I');
        
        for (auto i: S){
            if (i == curr)
                ++c;
            else{
                col.push_back({curr, c});
                c = 1;
                curr = i;
            }
        }               
        if (S.back() == 'I')
            ++c;
        col.push_back({curr, c});
        
        string out;
        c = 1;
        for (auto i: col){
            char op = i.first;
            int cnt = i.second + (op == 'D'? 1: -1);
            string temp;
            while (cnt--){
                temp += (char)('0' + c++);
            }
            if (op == 'D')
                reverse(temp.begin(), temp.end());
            out += temp;
        }
        return out;
    }
};

Contribution and Support

For discussions, questions, or doubts related to this solution, please visit our discussion section. We welcome your input and aim to foster a collaborative learning environment.

If you find this solution helpful, consider supporting us by giving a ⭐ star to the getlost01/gfg-potd repository.