LeetCode 484 - Find Permutation

The problem gives us a string s consisting only of the characters 'I' and 'D'. This string describes the relationship between adjacent numbers in a hidden permutation.

leetcodemediumarraystringstackgreedy

LeetCode Problem 484

Difficulty: 🟡 Medium
Topics: Array, String, Stack, Greedy

Solution

Problem Understanding

The problem gives us a string s consisting only of the characters 'I' and 'D'. This string describes the relationship between adjacent numbers in a hidden permutation.

If s[i] == 'I', then the permutation must satisfy:

perm[i] < perm[i + 1]

If s[i] == 'D', then the permutation must satisfy:

perm[i] > perm[i + 1]

Since the string has length n - 1, the resulting permutation must contain exactly n numbers, specifically all integers from 1 to n without repetition.

The task is not just to find any valid permutation. We must return the lexicographically smallest valid permutation.

Lexicographical order works similarly to dictionary order. When comparing two arrays, we compare elements from left to right. The first smaller element determines the smaller permutation. For example:

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

because 2 < 3 at the first position.

The constraints are important:

1 <= s.length <= 100000

This means the solution must be highly efficient. Any factorial or exponential approach is impossible because permutations grow extremely quickly. Even an O(n^2) solution may become risky for the upper bound. An O(n) solution is ideal.

There are several important edge cases to think about:

  • A string containing only 'I', such as "III", should produce the naturally increasing permutation [1,2,3,4].
  • A string containing only 'D', such as "DDD", should produce the decreasing permutation [4,3,2,1].
  • Alternating patterns like "DIDID" can expose ordering mistakes.
  • Long consecutive 'D' sequences are particularly important because they require reversing local ranges to maintain lexicographical minimality.
  • The input is guaranteed to contain only 'I' and 'D', so we do not need to handle invalid characters.

Approaches

Brute Force Approach

The brute force solution would generate every possible permutation of numbers from 1 to n, then check whether each permutation matches the pattern described by s.

For every permutation:

  • Compare adjacent elements.
  • Verify whether each pair satisfies the corresponding 'I' or 'D' condition.
  • Among all valid permutations, return the lexicographically smallest one.

This approach is correct because it exhaustively checks all possibilities. However, it is completely impractical.

If the string length is n - 1, then there are n! possible permutations. Even for relatively small values like n = 12, the number of permutations becomes enormous.

Because the constraint allows up to 100000 characters, brute force is impossible.

Optimal Greedy Approach

The key observation is that lexicographical minimality means we should place the smallest possible numbers as early as possible.

If we initially write the numbers in increasing order:

1, 2, 3, 4, 5, ...

then all 'I' conditions are already satisfied automatically.

The only challenge comes from consecutive 'D' segments.

For example:

s = "DDI"

The increasing sequence is:

1 2 3 4

But the first two relationships must be decreasing:

? > ? > ?

To satisfy this while keeping the permutation as small as possible lexicographically, we reverse only the minimal necessary segment.

Reversing the first three numbers gives:

3 2 1 4

This is the smallest valid arrangement.

The core greedy insight is:

  • Start with numbers 1 through n.
  • Whenever we encounter a consecutive block of 'D', reverse the corresponding segment in the permutation.
  • Reverse only the exact required range, nothing larger.

This produces the lexicographically smallest valid permutation in linear time.

Approach Time Complexity Space Complexity Notes
Brute Force O(n! × n) O(n) Generates every permutation and validates each one
Optimal Greedy O(n) O(n) Reverses segments corresponding to consecutive 'D' runs

Algorithm Walkthrough

Optimal Greedy Algorithm

  1. Create an initial permutation containing numbers from 1 to n, where n = len(s) + 1.

For example, if:

s = "DIID"

then initialize:

perm = [1,2,3,4,5]

This arrangement is already lexicographically smallest before applying constraints. 2. Traverse the string from left to right.

At each position, check whether the current character is 'D'. 3. When a 'D' is found, mark the start of a decreasing segment.

Continue moving forward while consecutive characters remain 'D'.

For example:

s = "IDDDI"

The substring "DDD" forms one decreasing block. 4. Reverse the corresponding range in the permutation.

Suppose the 'D' block starts at index start and ends at index end.

Then reverse:

perm[start : end + 2]

The extra +1 is necessary because relationships connect adjacent numbers, meaning a block of length k affects k + 1 numbers. 5. Continue scanning after the reversed segment. 6. Once the entire string has been processed, return the resulting permutation.

Why it works

The algorithm maintains the smallest possible numbers at the earliest positions. Initially using increasing order guarantees minimal lexicographical order globally.

Whenever a decreasing relationship is required, reversing only the minimal necessary contiguous range creates exactly the required descending structure while disturbing as little of the array as possible.

Any larger modification would place unnecessarily larger numbers earlier in the permutation, making the result lexicographically larger.

Therefore, the algorithm always constructs the lexicographically smallest valid permutation.

Python Solution

from typing import List

class Solution:
    def findPermutation(self, s: str) -> List[int]:
        n = len(s) + 1
        
        # Start with the lexicographically smallest arrangement
        perm = list(range(1, n + 1))
        
        i = 0
        
        while i < len(s):
            if s[i] == 'D':
                start = i
                
                # Find the entire consecutive D segment
                while i < len(s) and s[i] == 'D':
                    i += 1
                
                # Reverse the affected range
                perm[start:i + 1] = reversed(perm[start:i + 1])
            else:
                i += 1
        
        return perm

The implementation begins by constructing the increasing sequence [1,2,3,...,n]. This guarantees the smallest possible lexicographical starting point.

The variable i scans through the pattern string.

Whenever the algorithm encounters an 'I', nothing must be changed because the current increasing arrangement already satisfies the condition.

When a 'D' is encountered, the algorithm records the beginning of the decreasing block using start. It then advances until the entire consecutive 'D' sequence has been identified.

After locating the full segment, the corresponding portion of the permutation is reversed. This transforms the local increasing order into decreasing order while keeping the rest of the permutation unchanged.

Python slicing makes the reversal concise:

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

The range includes i + 1 because a block of k relationships involves k + 1 numbers.

Finally, the completed permutation is returned.

Go Solution

func findPermutation(s string) []int {
	n := len(s) + 1

	// Start with increasing order
	perm := make([]int, n)
	for i := 0; i < n; i++ {
		perm[i] = i + 1
	}

	i := 0

	for i < len(s) {
		if s[i] == 'D' {
			start := i

			// Find the full consecutive D segment
			for i < len(s) && s[i] == 'D' {
				i++
			}

			// Reverse the affected range
			reverse(perm, start, i)
		} else {
			i++
		}
	}

	return perm
}

func reverse(arr []int, left int, right int) {
	for left < right {
		arr[left], arr[right] = arr[right], arr[left]
		left++
		right--
	}
}

The Go implementation follows the same logic as the Python version but performs the reversal manually because Go slices do not support built in reverse operations.

The helper function reverse swaps elements from both ends toward the center.

Go slices are references to underlying arrays, so reversing the slice modifies the original permutation directly without extra copying.

No special overflow handling is needed because all values remain within the range [1, n], where n <= 100001.

Worked Examples

Example 1

Input:

s = "I"

Initial permutation:

[1,2]
Step Character Action Permutation
0 I No change needed [1,2]

Final result:

[1,2]

This satisfies:

1 < 2

Example 2

Input:

s = "DI"

Initial permutation:

[1,2,3]
Step Character Action Permutation
0 D Start D block at 0 [1,2,3]
0-0 D block Reverse indices 0 to 1 [2,1,3]
1 I No change needed [2,1,3]

Final result:

[2,1,3]

Verification:

2 > 1
1 < 3

Additional Example

Input:

s = "DDI"

Initial permutation:

[1,2,3,4]
Step Character Action Permutation
0 D Start D block [1,2,3,4]
0-1 DD Reverse indices 0 to 2 [3,2,1,4]
2 I No change [3,2,1,4]

Final result:

[3,2,1,4]

Verification:

3 > 2
2 > 1
1 < 4

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each index is visited at most a constant number of times
Space O(n) The output permutation itself requires linear space

The algorithm scans through the string once. Every element participates in at most one reversal operation, so the total work across all reversals remains linear.

The output array itself contains n integers, which dominates the space complexity.

Test Cases

from typing import List

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

        i = 0

        while i < len(s):
            if s[i] == 'D':
                start = i

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

                perm[start:i + 1] = reversed(perm[start:i + 1])
            else:
                i += 1

        return perm

sol = Solution()

assert sol.findPermutation("I") == [1, 2]  # single increasing relation
assert sol.findPermutation("D") == [2, 1]  # single decreasing relation
assert sol.findPermutation("DI") == [2, 1, 3]  # example from prompt
assert sol.findPermutation("ID") == [1, 3, 2]  # increasing then decreasing
assert sol.findPermutation("III") == [1, 2, 3, 4]  # all increasing
assert sol.findPermutation("DDD") == [4, 3, 2, 1]  # all decreasing
assert sol.findPermutation("DID") == [2, 1, 4, 3]  # alternating pattern
assert sol.findPermutation("IIDDD") == [1, 2, 6, 5, 4, 3]  # trailing D block
assert sol.findPermutation("DDDI") == [4, 3, 2, 1, 5]  # leading D block
assert sol.findPermutation("IDIDID") == [1, 3, 2, 5, 4, 7, 6]  # alternating multiple times
Test Why
"I" Simplest increasing case
"D" Simplest decreasing case
"DI" Official example
"ID" Mixed ordering
"III" No reversals needed
"DDD" Entire permutation reversed
"DID" Alternating pattern
"IIDDD" Long decreasing suffix
"DDDI" Long decreasing prefix
"IDIDID" Multiple independent reversals

Edge Cases

All Increasing Characters

A string like:

"IIII"

is important because the algorithm should recognize that no reversals are necessary. A buggy implementation might still attempt unnecessary operations or mishandle boundaries.

The current implementation handles this naturally because it only performs work when encountering 'D'.

All Decreasing Characters

A string like:

"DDDD"

creates one large decreasing block affecting the entire permutation.

This case is easy to mishandle because the reversal range must include all involved numbers, specifically length + 1 elements.

The implementation correctly reverses the entire array:

[1,2,3,4,5] -> [5,4,3,2,1]

Consecutive Decreasing Segments

Inputs such as:

"IIDDDI"

are important because consecutive 'D' characters must be processed as one unified block rather than individual reversals.

If each 'D' were reversed separately, the result would not satisfy all conditions simultaneously.

The implementation explicitly scans forward to identify the complete consecutive 'D' run before performing exactly one reversal on the affected range.