6Companies30days

Number following a pattern

Given a pattern containing only I’s and D’s. I for increasing and D for decreasing. Devise an algorithm to print the minimum number following that pattern. Digits from 1-9 and digits can’t repeat.

Example

Input:
D
Output:
21
Explanation:
D is meant for decreasing,
So we choose the minimum number
among 21,31,54,87,etc.

Solution

    string printMinNumberForPattern(string str){
    string ans = ""; // Minimum number following pattern
 
    int i = 0;
    int cur = 1; // cur val following pattern
    int dCount = 0; // Count of char 'D'
    while (i < str.length()) {
 
        char ch = str[i];
 
        // If 1st ch == 'I', incr and add to ans
        if (i == 0 && ch == 'I') {
            ans += to_string(cur);
            cur++;
        }
 
        // If cur char == 'D',
        // incr dCount as well, since we always
        // start counting for dCount from i+1
        if (ch == 'D') {
            dCount++;
        }
 
        int j = i + 1; // Count 'D' from i+1 index
        while (j < str.length()
               && str[j] == 'D') {
            dCount++;
            j++;
        }
 
        int k = dCount;  // Store dCount
        while (dCount >= 0) {
            ans += to_string(cur + dCount);
            dCount--;
        }
 
        cur += (k + 1); // Manages next cur val
        dCount = 0;
        i = j;
    }
 
    return ans;
        
    }