LeetCode 484: Find Permutation

Problem Restatement

We are given a string s made only of two characters:

We need to return the lexicographically smallest permutation of numbers from 1 to n, where:

n = len(s) + 1

The permutation must match the pattern in s.

For each index i:

The input length is positive and at most 10000.

Input and Output

Function shape:

def findPermutation(s: str) -> list[int]:
    ...

Examples

Example 1:

s = "I"

We need two numbers.

The pattern says the first number must be smaller than the second.

The smallest valid permutation is:

[1, 2]

Example 2:

s = "DI"

We need three numbers.

The pattern means:

perm[0] > perm[1] < perm[2]

Valid permutations include:

[2, 1, 3]
[3, 1, 2]

The lexicographically smaller one is:

[2, 1, 3]

So the answer is:

[2, 1, 3]

First Thought: Try Permutations

A direct idea is to generate every permutation of 1..n, then return the first one that matches the pattern.

This works for tiny input only.

For example, for s = "DI", n = 3, we could check all permutations of [1, 2, 3].

But for large n, this is impossible because there are n! permutations.

We need to construct the answer directly.

Key Insight

Start with the smallest possible increasing list:

1 2 3 4 5 ...

This is already lexicographically smallest.

The only problem comes from runs of D.

For a decreasing run, we need the numbers in that segment to go down.

For example:

s = "DDI"

We need:

perm[0] > perm[1] > perm[2] < perm[3]

Start with:

1 2 3 4

The first three positions must decrease, so reverse that block:

3 2 1 4

Now:

3 > 2 > 1 < 4

This is also lexicographically smallest because we used the smallest possible numbers in the earliest block.

So every consecutive run of Ds should reverse the corresponding block of numbers.

Algorithm

Create the initial answer:

ans = [1, 2, 3, ..., len(s) + 1]

Scan the pattern string.

Whenever we find a run of Ds from index i to index j - 1, reverse:

ans[i : j + 1]

Why j + 1?

Because a run of r D characters connects r + 1 numbers.

For example:

s = "DDD"

has three decreasing relations:

ans[0] > ans[1] > ans[2] > ans[3]

So we reverse four numbers.

Correctness

The initial array contains every number from 1 to n exactly once.

The algorithm only reverses subarrays, so the final result is still a permutation of 1..n.

Consider any maximal run of Ds in s, from index i to index j - 1.

The algorithm reverses ans[i : j + 1].

Before reversing, that block is increasing:

i + 1, i + 2, ..., j + 1

After reversing, the block is decreasing:

j + 1, j, ..., i + 1

Therefore, every D relation inside that run is satisfied.

For an I relation between two runs, the right side begins after the reversed block. Since the construction uses increasing ranges of numbers, the first value after the block is larger than the smallest value at the end of the reversed block. Therefore, the I relation is also satisfied.

The result is lexicographically smallest because each decreasing run is fixed using the smallest consecutive numbers that can satisfy the run. Any valid solution for a run of r Ds must place at least r + 1 distinct numbers in decreasing order. The smallest possible first number for that run is therefore the largest number in the smallest available block of size r + 1. Reversing the initial increasing array achieves exactly that. Since this is done from left to right, no earlier position can be made smaller without breaking the required D run.

Thus the algorithm returns the lexicographically smallest valid permutation.

Complexity

Here, n = len(s) + 1.

Implementation

class Solution:
    def findPermutation(self, s: str) -> list[int]:
        n = len(s) + 1
        ans = list(range(1, n + 1))

        i = 0

        while i < len(s):
            if s[i] == "I":
                i += 1
                continue

            start = i

            while i < len(s) and s[i] == "D":
                i += 1

            ans[start:i + 1] = reversed(ans[start:i + 1])

        return ans

Code Explanation

We first create the smallest increasing permutation:

ans = list(range(1, n + 1))

Then we scan the pattern:

i = 0

while i < len(s):

If the current relation is already increasing, nothing needs to change:

if s[i] == "I":
    i += 1
    continue

When we see D, we record the start of the decreasing run:

start = i

Then move until the run ends:

while i < len(s) and s[i] == "D":
    i += 1

If the run covers pattern indices start through i - 1, it covers answer indices start through i.

So we reverse:

ans[start:i + 1] = reversed(ans[start:i + 1])

Finally, return the constructed permutation.

Stack Implementation

Another common solution uses a stack.

Push numbers as we scan. Whenever we see I, flush the stack. Flushing reverses the previous run of Ds.

class Solution:
    def findPermutation(self, s: str) -> list[int]:
        ans = []
        stack = []

        for i, ch in enumerate(s):
            stack.append(i + 1)

            if ch == "I":
                while stack:
                    ans.append(stack.pop())

        stack.append(len(s) + 1)

        while stack:
            ans.append(stack.pop())

        return ans

This produces the same result.

Testing

def run_tests():
    s = Solution()

    assert s.findPermutation("I") == [1, 2]
    assert s.findPermutation("DI") == [2, 1, 3]
    assert s.findPermutation("DDI") == [3, 2, 1, 4]
    assert s.findPermutation("ID") == [1, 3, 2]
    assert s.findPermutation("DIDI") == [2, 1, 4, 3, 5]
    assert s.findPermutation("III") == [1, 2, 3, 4]
    assert s.findPermutation("DDD") == [4, 3, 2, 1]

    print("all tests passed")

run_tests()

Test meaning: