LeetCode 942 - DI String Match

In this problem, we are given a string s consisting only of the characters 'I' and 'D'. The string has length n, and we must construct a permutation of the integers from 0 to n, inclusive. A permutation means every number in the range appears exactly once.

leetcodeeasyarraytwo-pointersstringgreedy

LeetCode Problem 942

Difficulty: 🟢 Easy
Topics: Array, Two Pointers, String, Greedy

Solution

Problem Understanding

In this problem, we are given a string s consisting only of the characters 'I' and 'D'. The string has length n, and we must construct a permutation of the integers from 0 to n, inclusive.

A permutation means every number in the range appears exactly once. Since the range is [0, n], the resulting array must contain exactly n + 1 elements.

The meaning of the characters is determined by the relative ordering between adjacent elements in the permutation:

  • If s[i] == 'I', then perm[i] < perm[i + 1]
  • If s[i] == 'D', then perm[i] > perm[i + 1]

The goal is to return any valid permutation that satisfies all these relationships.

For example, if the input is:

s = "IDID"

then we need a permutation of [0,1,2,3,4] such that:

  • index 0 is increasing
  • index 1 is decreasing
  • index 2 is increasing
  • index 3 is decreasing

One valid answer is:

[0,4,1,3,2]

because:

  • 0 < 4
  • 4 > 1
  • 1 < 3
  • 3 > 2

The constraints are important:

  • 1 <= s.length <= 10^5

This means the solution must be highly efficient. Any factorial-time or exponential approach is impossible because the number of permutations grows extremely quickly. Even an O(n^2) solution is less desirable when n becomes very large.

The problem guarantees:

  • Every character is either 'I' or 'D'
  • A valid permutation always exists

Important edge cases include strings made entirely of 'I', strings made entirely of 'D', and alternating patterns such as "IDIDID". These patterns can expose flaws in naive greedy strategies if the implementation does not carefully maintain valid remaining numbers.

Approaches

Brute Force Approach

A brute-force solution would generate every possible permutation of the integers [0, n] and check whether it satisfies the pattern described by s.

For each permutation, we would iterate through the string and verify:

  • if s[i] == 'I', then perm[i] < perm[i + 1]
  • if s[i] == 'D', then perm[i] > perm[i + 1]

The first valid permutation could then be returned.

This approach is correct because it exhaustively checks all possible candidates. Eventually, it will find a valid permutation since the problem guarantees one exists.

However, this method is far too slow. The number of permutations of n + 1 elements is:

$$(n + 1)!$$

Even for relatively small values of n, factorial growth becomes computationally infeasible. Since n can be as large as 100000, brute force is completely impractical.

Optimal Greedy Two-Pointer Approach

The key observation is that we do not need to try every permutation. Instead, we can construct a valid permutation greedily.

At every position, we only care about whether the next relationship should be increasing or decreasing.

We maintain two available numbers:

  • low, the smallest unused number
  • high, the largest unused number

Initially:

low = 0
high = n

Then we process the string character by character:

  • If we see 'I', we place the smallest available number.

  • This guarantees the next number can still be larger.

  • If we see 'D', we place the largest available number.

  • This guarantees the next number can still be smaller.

After using a number, we move the corresponding pointer inward.

At the end, exactly one number remains unused, and we append it.

This works because each decision preserves enough flexibility for future positions while immediately satisfying the current constraint.

Approach Time Complexity Space Complexity Notes
Brute Force O((n + 1)! * n) O(n) Generates every permutation and validates each one
Optimal O(n) O(n) Greedy construction using two pointers

Algorithm Walkthrough

  1. Initialize two pointers:
  • low = 0
  • high = n

These represent the smallest and largest unused values available for the permutation. 2. Create an empty result array.

This array will store the constructed permutation. 3. Iterate through each character in the string s.

At every step, we decide which number to place next. 4. If the current character is 'I':

  • Append low to the result.
  • Increment low.

We choose the smallest available number because the next number must be larger. 5. If the current character is 'D':

  • Append high to the result.
  • Decrement high.

We choose the largest available number because the next number must be smaller. 6. Continue processing until all characters in s are handled.

Since s has length n, we will append exactly n numbers during this loop. 7. One number will remain unused.

At this point, low == high. 8. Append the final remaining number to the result.

This completes the permutation of size n + 1.

Why it works

The algorithm maintains an important invariant:

  • All unused numbers are always within the range [low, high].

When we encounter 'I', selecting the smallest available value guarantees there is still some larger number available later.

When we encounter 'D', selecting the largest available value guarantees there is still some smaller number available later.

Because each choice immediately satisfies the current condition while preserving valid future options, the final permutation always satisfies the entire pattern.

Python Solution

from typing import List

class Solution:
    def diStringMatch(self, s: str) -> List[int]:
        low = 0
        high = len(s)

        result = []

        for char in s:
            if char == 'I':
                result.append(low)
                low += 1
            else:
                result.append(high)
                high -= 1

        result.append(low)

        return result

The implementation follows the greedy strategy directly.

We first initialize low and high to represent the smallest and largest unused numbers. Since the permutation must contain all integers from 0 to n, the initial range is exactly [0, len(s)].

The loop processes each character in the string:

  • For 'I', the code appends the smallest available number and advances low.
  • For 'D', the code appends the largest available number and decreases high.

At every step, one value is consumed and removed from the available range.

After the loop finishes, exactly one unused number remains. Because all numbers between low and high have been consumed except one, we know low == high. Appending this final value completes the permutation.

The implementation runs in linear time and uses only the output array as extra storage.

Go Solution

func diStringMatch(s string) []int {
    low := 0
    high := len(s)

    result := make([]int, 0, len(s)+1)

    for _, ch := range s {
        if ch == 'I' {
            result = append(result, low)
            low++
        } else {
            result = append(result, high)
            high--
        }
    }

    result = append(result, low)

    return result
}

The Go implementation mirrors the Python solution closely.

A slice is created with capacity len(s) + 1 to avoid unnecessary reallocations during appends. The algorithm still uses the same low and high pointer strategy.

Go uses rune iteration in the for _, ch := range s loop, which works correctly because the input contains only ASCII characters.

There are no integer overflow concerns because the maximum value is at most 100000, which easily fits within Go's int type.

Worked Examples

Example 1

s = "IDID"

Initial state:

low = 0
high = 4
result = []
Step Character Action Result low high
1 I append low [0] 1 4
2 D append high [0,4] 1 3
3 I append low [0,4,1] 2 3
4 D append high [0,4,1,3] 2 2

After the loop:

append remaining value 2

Final result:

[0,4,1,3,2]

Validation:

0 < 4
4 > 1
1 < 3
3 > 2

Example 2

s = "III"

Initial state:

low = 0
high = 3
result = []
Step Character Action Result low high
1 I append low [0] 1 3
2 I append low [0,1] 2 3
3 I append low [0,1,2] 3 3

Append remaining value:

3

Final result:

[0,1,2,3]

Example 3

s = "DDI"

Initial state:

low = 0
high = 3
result = []
Step Character Action Result low high
1 D append high [3] 0 2
2 D append high [3,2] 0 1
3 I append low [3,2,0] 1 1

Append remaining value:

1

Final result:

[3,2,0,1]

Validation:

3 > 2
2 > 0
0 < 1

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each character in the string is processed exactly once
Space O(n) The output permutation contains n + 1 integers

The algorithm performs a single pass through the input string. Every iteration executes only constant-time operations such as comparisons, appends, and pointer updates.

The extra space usage comes entirely from the result array. Aside from the output itself, only a few integer variables are maintained.

Test Cases

from typing import List

class Solution:
    def diStringMatch(self, s: str) -> List[int]:
        low = 0
        high = len(s)

        result = []

        for char in s:
            if char == 'I':
                result.append(low)
                low += 1
            else:
                result.append(high)
                high -= 1

        result.append(low)

        return result

def is_valid(s: str, perm: List[int]) -> bool:
    n = len(s)

    # Must contain all numbers from 0 to n exactly once
    if sorted(perm) != list(range(n + 1)):
        return False

    # Must satisfy I/D conditions
    for i, ch in enumerate(s):
        if ch == 'I' and not (perm[i] < perm[i + 1]):
            return False
        if ch == 'D' and not (perm[i] > perm[i + 1]):
            return False

    return True

sol = Solution()

# Provided example 1
result = sol.diStringMatch("IDID")
assert is_valid("IDID", result)

# Provided example 2
result = sol.diStringMatch("III")
assert is_valid("III", result)

# Provided example 3
result = sol.diStringMatch("DDI")
assert is_valid("DDI", result)

# Smallest possible input
result = sol.diStringMatch("I")
assert is_valid("I", result)

# Single decreasing relationship
result = sol.diStringMatch("D")
assert is_valid("D", result)

# All increasing pattern
result = sol.diStringMatch("IIII")
assert is_valid("IIII", result)

# All decreasing pattern
result = sol.diStringMatch("DDDD")
assert is_valid("DDDD", result)

# Alternating pattern
result = sol.diStringMatch("IDIDID")
assert is_valid("IDIDID", result)

# Opposite alternating pattern
result = sol.diStringMatch("DIDIDI")
assert is_valid("DIDIDI", result)

# Larger mixed case
result = sol.diStringMatch("IIDDDIDIDI")
assert is_valid("IIDDDIDIDI", result)

print("All tests passed!")
Test Why
"IDID" Verifies alternating increasing and decreasing behavior
"III" Tests all increasing relationships
"DDI" Tests consecutive decreasing relationships followed by increasing
"I" Smallest valid increasing input
"D" Smallest valid decreasing input
"IIII" Ensures monotonic increasing construction works
"DDDD" Ensures monotonic decreasing construction works
"IDIDID" Tests frequent pointer switching
"DIDIDI" Tests alternating pattern beginning with decreasing
"IIDDDIDIDI" Larger mixed pattern stress test

Edge Cases

One important edge case is a string consisting entirely of 'I' characters, such as "IIII". A buggy implementation might accidentally reuse values or fail to maintain increasing order throughout the array. The greedy strategy handles this naturally by always taking the smallest remaining value. The resulting permutation becomes strictly increasing.

Another critical edge case is a string consisting entirely of 'D' characters, such as "DDDD". This can expose issues in implementations that do not correctly preserve smaller future values. The algorithm handles this by repeatedly choosing the largest available number, guaranteeing that every adjacent pair remains decreasing.

Alternating patterns like "IDIDID" are also important because they force the algorithm to switch repeatedly between the smallest and largest remaining values. A naive greedy strategy could easily paint itself into a corner and leave no valid number for later positions. The two-pointer method avoids this problem because every choice intentionally preserves the opposite side of the range for future use.

A final subtle edge case is the smallest possible input size, where s.length == 1. The algorithm still works correctly because there are exactly two numbers available, [0,1], and the first character immediately determines their order. The final append operation correctly places the remaining value.