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.
Examples:
Input: D Output: 21
Input: I Output: 12
Input: DD Output: 321
Input: II Output: 123
Input: DIDI Output: 21435
Input: IIDDD Output: 126543
Input: DDIDDIID Output: 321654798
/**
* When first 'I' comes in input is the place where we have to print 1 and for
* all the 'D' before 'I' we print grater than 1 in series
*
* Like if we have DDID First i comes at 3rd place so we print 1 at 3rd place
*
* So it will be like 321 And in code firstly we find max num is length of
* string + 1 So here we have 5 and we already print 321 now we print remaining
* from 5 to grater than 3 so it will be like 32154 and it's the output
*/
public class solution {
static String getMinNumberForPattern(String str) {
int n = str.length();
if (n >= 9)
return "-1";
char result[] = new char[n + 1];
int lastI = -1;
int currentValueToPut = 1;
// O(n) -> Every character is traversed twice
for (int i = 0; i <= n; i++) {
// Find 'I' OR END of string
if (i == n || str.charAt(i) == 'I') {
// Putting values in increasing order (in reverse) to get decreasing order in
// correct direction
for (int j = i; j > lastI; j--) {
char digit = (char) (currentValueToPut + '0');
result[j] = digit;
currentValueToPut++;
}
lastI = i;
}
}
return new String(result);
}
public static void main(String[] args) {
String inputs[] = { "IDID", "I", "DD", "II", "DIDI", "IIDDD", "DDIDDIID" };
for (String input : inputs) {
System.out.println(input + " -> " + getMinNumberForPattern(input));
}
}
}