LeetCode 942: DI String Match

Problem Restatement

We are given a string s of length n.

Each character is either:

"I"

or:

"D"

We need to return any permutation perm of the integers from 0 to n such that:

If multiple answers exist, any valid answer is accepted. The official statement defines the same reconstruction task for a permutation of [0, n].

Input and Output

Function shape:

class Solution:
    def diStringMatch(self, s: str) -> list[int]:
        ...

Examples

Example 1:

s = "IDID"

One valid answer is:

[0, 4, 1, 3, 2]

Check each relation:

Example 2:

s = "III"

A valid answer is:

[0, 1, 2, 3]

Every adjacent pair increases.

Example 3:

s = "DDI"

A valid answer is:

[3, 2, 0, 1]

The first two relations decrease, and the last relation increases.

These examples match the official examples.

First Thought: Try Permutations

A direct method is to generate every permutation of:

[0, 1, 2, ..., n]

Then test whether it satisfies the pattern.

This is not practical.

There are (n + 1)! permutations, while n can be up to 10^5. We need to construct a valid answer directly.

Key Insight

Use the smallest and largest remaining numbers.

Keep two pointers:

When we see "I", we need the current value to be smaller than the next value.

So we can safely place the smallest remaining number.

When we see "D", we need the current value to be larger than the next value.

So we can safely place the largest remaining number.

This works because choosing an extreme value guarantees that the next value can satisfy the relation.

Algorithm

Initialize:

low = 0
high = len(s)
ans = []

For each character c in s:

If c == "I":

ans.append(low)
low += 1

If c == "D":

ans.append(high)
high -= 1

After processing all characters, exactly one number remains.

Append it:

ans.append(low)

Return ans.

Walkthrough

Use:

s = "IDID"

Start:

low = 0
high = 4
ans = []

Append the last remaining value:

[0, 4, 1, 3, 2]

This satisfies "IDID".

Correctness

The algorithm always uses each number at most once because it only takes from the current unused range [low, high], then moves one boundary inward.

When the current character is "I", the algorithm appends low, the smallest unused number. The next number must come from the remaining range, where every value is greater than low. Therefore, the required relation perm[i] < perm[i + 1] can be satisfied.

When the current character is "D", the algorithm appends high, the largest unused number. The next number must come from the remaining range, where every value is smaller than high. Therefore, the required relation perm[i] > perm[i + 1] can be satisfied.

After processing all n characters, one unused number remains. Appending it completes a permutation of all integers from 0 to n.

Each relation was made valid at the moment its left value was chosen, so the final array satisfies every character in s.

Complexity

Implementation

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

        for c in s:
            if c == "I":
                ans.append(low)
                low += 1
            else:
                ans.append(high)
                high -= 1

        ans.append(low)
        return ans

Code Explanation

low starts as the smallest available number:

low = 0

high starts as the largest available number:

high = len(s)

For an increasing relation, use the smallest available value:

if c == "I":
    ans.append(low)
    low += 1

For a decreasing relation, use the largest available value:

else:
    ans.append(high)
    high -= 1

At the end, low == high, so either value is the last remaining number:

ans.append(low)

Testing

def is_valid(s, perm):
    n = len(s)

    if sorted(perm) != list(range(n + 1)):
        return False

    for i, c in enumerate(s):
        if c == "I" and not (perm[i] < perm[i + 1]):
            return False

        if c == "D" and not (perm[i] > perm[i + 1]):
            return False

    return True

def run_tests():
    sol = Solution()

    ans = sol.diStringMatch("IDID")
    assert is_valid("IDID", ans)

    ans = sol.diStringMatch("III")
    assert is_valid("III", ans)

    ans = sol.diStringMatch("DDI")
    assert is_valid("DDI", ans)

    ans = sol.diStringMatch("I")
    assert is_valid("I", ans)

    ans = sol.diStringMatch("D")
    assert is_valid("D", ans)

    ans = sol.diStringMatch("DIDDI")
    assert is_valid("DIDDI", ans)

    print("all tests passed")

run_tests()