DI String Match

easy greedy two pointers string

Problem

A permutation perm of the integers in the range [0, n] is encoded by a string s of length n where s[i] == 'I' means perm[i] < perm[i+1] and s[i] == 'D' means perm[i] > perm[i+1]. Given such a string s, reconstruct and return any permutation perm that matches it. There is always at least one valid answer.

Inputs = "IDID"

Output[0, 4, 1, 3, 2]

n = 4, so the permutation uses 0..4. Each 'I' rises and each 'D' falls: 0<4, 4>1, 1<3, 3>2.

s (only I and D)

def di_string_match(s):
    low, high = 0, len(s)
    perm = []
    for ch in s:
        if ch == 'I':
            perm.append(low)
            low += 1
        else:
            perm.append(high)
            high -= 1
    perm.append(low)
    return perm

function diStringMatch(s) {
  let low = 0, high = s.length;
  const perm = [];
  for (const ch of s) {
    if (ch === 'I') {
      perm.push(low);
      low++;
    } else {
      perm.push(high);
      high--;
    }
  }
  perm.push(low);
  return perm;
}

class Solution {
    public int[] diStringMatch(String s) {
        int low = 0, high = s.length();
        int[] perm = new int[s.length() + 1];
        int idx = 0;
        for (char ch : s.toCharArray()) {
            if (ch == 'I') perm[idx++] = low++;
            else perm[idx++] = high--;
        }
        perm[idx] = low;
        return perm;
    }
}

vector<int> diStringMatch(string s) {
    int low = 0, high = (int)s.size();
    vector<int> perm;
    for (char ch : s) {
        if (ch == 'I') perm.push_back(low++);
        else perm.push_back(high--);
    }
    perm.push_back(low);
    return perm;
}

Explanation

We need a permutation of 0..n that goes up on every 'I' and down on every 'D'. The neat trick is to keep a running low and high pointer and hand out the smallest unused number when we must go up, and the largest unused number when we must go down.

We start with low = 0 and high = n. For each character: on 'I' we append low and bump it up; on 'D' we append high and bump it down. Whatever single number remains at the end (low, which now equals high) is appended last.

Why it always works: when we place low for an 'I', every number we will place afterward is larger, so the next element is guaranteed bigger. When we place high for a 'D', every remaining number is smaller, guaranteeing the next element is smaller. The constraint at each step is satisfied no matter what follows.

Example: s="IDID", so n=4, low=0, high=4. I→0, D→4, I→1, D→3, then append low=2, giving [0, 4, 1, 3, 2].

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