DI String Match

Difficulty: Easy | Acceptance: 81.00% | Paid: No Topics: Array, Two Pointers, String, Greedy

A permutation perm of n + 1 integers of all the integers in the range [0, n] can be represented as a string s of length n where:

• s[i] == ‘I’ if perm[i] < perm[i + 1], and
• s[i] == ‘D’ if perm[i] > perm[i + 1].

Given a string s, reconstruct the permutation perm and return it. If there are multiple valid permutations perm, return any of them.

• Examples
• Constraints
• Two Pointers (Greedy)
• Stack-based Approach
• Reverse Segments

Examples

Example 1

Input: s = "IDID"
Output: [0,4,1,3,2]
Explanation: 
- perm[0] < perm[1] (0 < 4) matches 'I'
- perm[1] > perm[2] (4 > 1) matches 'D'
- perm[2] < perm[3] (1 < 3) matches 'I'
- perm[3] > perm[4] (3 > 2) matches 'D'

Example 2

Input: s = "III"
Output: [0,1,2,3]
Explanation: All positions require increase, so we use the smallest available numbers in order.

Example 3

Input: s = "DDDD"
Output: [4,3,2,1,0]
Explanation: All positions require decrease, so we use the largest available numbers in order.

Constraints

1 <= s.length <= 10⁵
s[i] is either 'I' or 'D'.

Two Pointers (Greedy)

Intuition Use two pointers to track the smallest and largest available numbers. For ‘I’, assign the smallest remaining number to ensure we can always find a larger number later. For ‘D’, assign the largest remaining number to ensure we can always find a smaller number later.

Steps

• Initialize low = 0 and high = n (where n = s.length())
• Iterate through each character in s:
  • If s[i] == ‘I’, assign low to result[i] and increment low
  • If s[i] == ‘D’, assign high to result[i] and decrement high
• Assign the remaining value (low == high) to the last position

class Solution:
    def diStringMatch(self, s: str) -> list[int]:
        n = len(s)
        result = [0] * (n + 1)
        low, high = 0, n
        
        for i, char in enumerate(s):
            if char == 'I':
                result[i] = low
                low += 1
            else:
                result[i] = high
                high -= 1
        
        result[n] = low
        return result

Complexity

• Time: O(n) - Single pass through the string
• Space: O(n) - For the result array (O(1) extra space)
• Notes: Optimal solution with minimal space usage

Stack-based Approach

Intuition Initialize the result with [0, 1, 2, …, n]. Use a stack to track indices where ‘D’ starts. When we encounter ‘I’ or reach the end, reverse all segments marked by ‘D’ to satisfy the decreasing requirement.

Steps

• Initialize result with [0, 1, 2, …, n]
• Use a stack to track start indices of ‘D’ segments
• Iterate through the string:
  • If s[i] == ‘D’, push i onto the stack
  • If s[i] == ‘I’ or i == n-1, pop all indices from stack and reverse the segment from that index to i+1
• Return the result

class Solution:
    def diStringMatch(self, s: str) -> list[int]:
        n = len(s)
        result = list(range(n + 1))
        stack = []
        
        for i, char in enumerate(s):
            if char == 'D':
                stack.append(i)
            else:
                while stack:
                    start = stack.pop()
                    result[start], result[i + 1] = result[i + 1], result[start]
        
        while stack:
            start = stack.pop()
            result[start], result[n] = result[n], result[start]
        
        return result

Complexity

• Time: O(n) - Each element is swapped at most once
• Space: O(n) - For the stack in worst case (all ‘D’s)
• Notes: More complex than two pointers but demonstrates a different pattern

Reverse Segments

Intuition Initialize result with [0, 1, 2, …, n]. Identify consecutive ‘D’ segments and reverse each segment to satisfy the decreasing requirement.

Steps

• Initialize result with [0, 1, 2, …, n]
• Find all consecutive segments of ‘D’ in the string
• For each segment from index i to j (inclusive), reverse result[i:j+2]
• Return the result

class Solution:
    def diStringMatch(self, s: str) -> list[int]:
        n = len(s)
        result = list(range(n + 1))
        i = 0
        
        while i < n:
            if s[i] == 'D':
                start = i
                while i < n and s[i] == 'D':
                    i += 1
                result[start:i + 1] = result[start:i + 1][::-1]
            else:
                i += 1
        
        return result

Complexity

• Time: O(n) - Each element is visited at most twice
• Space: O(1) - In-place reversal
• Notes: Intuitive approach that directly addresses the problem requirements