Find Permutation

medium stack greedy string

Problem

Given a string of "I" (increase) and "D" (decrease) characters of length n, return the lexicographically smallest permutation of 1..n+1 matching the pattern.

Inputs = "DI"

Output[2,1,3]

Stack pushes 1,2; "D" first means 1 < 2 reversed to 2,1; then "I" makes 1 < 3.

s (only I/D)

def find_permutation(s):
    out = []
    stack = []
    for i in range(len(s) + 1):
        stack.append(i + 1)
        if i == len(s) or s[i] == "I":
            while stack: out.append(stack.pop())
    return out

function findPermutation(s) {
  const out = [], stack = [];
  for (let i = 0; i <= s.length; i++) {
    stack.push(i + 1);
    if (i === s.length || s[i] === "I") {
      while (stack.length) out.push(stack.pop());
    }
  }
  return out;
}

class Solution {
    public int[] findPermutation(String s) {
        int n = s.length();
        int[] out = new int[n + 1];
        Deque stack = new ArrayDeque<>();
        int idx = 0;
        for (int i = 0; i <= n; i++) {
            stack.push(i + 1);
            if (i == n || s.charAt(i) == 'I') {
                while (!stack.isEmpty()) out[idx++] = stack.pop();
            }
        }
        return out;
    }
}

vector findPermutation(string s) {
    vector out;
    stack st;
    for (int i = 0; i <= (int)s.size(); i++) {
        st.push(i + 1);
        if (i == (int)s.size() || s[i] == 'I') {
            while (!st.empty()) { out.push_back(st.top()); st.pop(); }
        }
    }
    return out;
}

Explanation

We want the smallest permutation of 1..n+1 that matches a pattern of 'I' (increase) and 'D' (decrease). The clean idea: a run of Ds must be a decreasing block, and a stack naturally reverses a block when you flush it.

We push the numbers 1, 2, 3, ... in order. As long as we are inside a D-run we keep pushing, holding the numbers back. The moment we hit an 'I' (or reach the end), we pop everything off the stack into the output.

Popping reverses the held numbers, which turns the smallest available numbers into the required descending order for that D-block while keeping everything as small as possible — giving the lexicographically smallest result.

Example: s = "DI". Push 1, then 2 (the D keeps them held); the I flushes the stack, popping 2, 1. Then push 3 and flush at the end → output [2, 1, 3].

Every number is pushed once and popped once, so the whole process is linear.

Time: O(n) Space: O(n)