import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 思路：如果是字符‘I’直接对应的数字加入结果res中，如果是‘D’将对应的数字加入栈中。
 *       再次遇到‘I’先将对应的数字加入结果res中，然后再将栈中的元素从栈顶取出存放在
 *       res中，这样保证了‘D’对应的数字：num[i] > num[i + 1]
 *       (ps:根据示例模拟一遍能更好的理解：)
 * @auther start
 * @create 2024-01-01 22:06
 */
public class L2375 {
    public String smallestNumber(String pattern) {
        int n = pattern.length();
        //栈中存储‘D’所对应的数字
        Deque<Integer> stack = new ArrayDeque<>();
        StringBuilder res = new StringBuilder();
        //与字符串中的字符相对应，从1开始保证字典序最小
        int num = 1;
        for (int i = 0; i < n; i++) {
            char c = pattern.charAt(i);
            if (c == 'D') {
                stack.push(num);
            } else {
                res.append(num);
                while (!stack.isEmpty()) {
                    res.append(stack.pop());
                }
            }
            num++;
        }
        //根据题目要求，结果长度比pattern大1
        res.append(num);
        //取出栈中全部元素
        while (!stack.isEmpty()) {
            res.append(stack.pop());
        }
        return res.toString();
    }
}