484. Find Permutation 🔒
Problem Description
You are given a string s
of length n-1
consisting of characters 'I' and 'D' that describes the relationship between consecutive elements in a permutation.
A permutation perm
is an arrangement of all integers from 1 to n (where n = length of s + 1). The string s
encodes how consecutive elements in the permutation compare:
s[i] = 'I'
meansperm[i] < perm[i+1]
(increasing)s[i] = 'D'
meansperm[i] > perm[i+1]
(decreasing)
Your task is to find the lexicographically smallest permutation that satisfies the pattern described by string s
.
For example, if s = "DI"
, this means:
perm[0] > perm[1]
(first pair is decreasing)perm[1] < perm[2]
(second pair is increasing)
The permutation [2, 1, 3]
would satisfy this pattern and is the lexicographically smallest such permutation.
The solution approach starts with the natural sequence [1, 2, 3, ..., n+1]
and reverses segments wherever there are consecutive 'D' characters. This greedy strategy ensures we get the lexicographically smallest result by only making necessary swaps to satisfy the decreasing constraints while keeping the rest in ascending order.
Intuition
To find the lexicographically smallest permutation, we want to use the smallest available numbers as early as possible in our sequence. The natural starting point would be [1, 2, 3, ..., n+1]
, which is already the lexicographically smallest arrangement if there were no constraints.
Now, when we encounter an 'I' in the pattern string, we want consecutive numbers to be increasing - which they already are in our initial sequence [1, 2, 3, ...]
. So 'I' positions don't require any changes.
The challenge comes with 'D' positions. When we see a 'D', we need the current number to be greater than the next one. If we have consecutive 'D's, we need a sequence of decreasing numbers.
The key insight is that to maintain the lexicographically smallest property while satisfying the 'D' constraints, we should reverse only the segments that correspond to consecutive 'D's.
For example, if we have the pattern "DDII" starting with [1, 2, 3, 4, 5]
:
- The first two 'D's mean positions 0, 1, 2 must be decreasing
- We reverse
[1, 2, 3]
to get[3, 2, 1]
- The final sequence becomes
[3, 2, 1, 4, 5]
This approach is optimal because:
- We only disturb the natural ascending order where absolutely necessary (at 'D' positions)
- By reversing consecutive 'D' segments, we use the smallest possible numbers that can satisfy the decreasing constraint
- The remaining positions keep their natural ascending order, maintaining lexicographic minimality
The algorithm scans for consecutive 'D's, reverses the corresponding segment in our answer array (including one position after the last 'D'), and continues until the entire pattern is processed.
Solution Approach
The implementation uses a greedy algorithm with segment reversal to construct the lexicographically smallest permutation:
-
Initialize the base permutation: Start with
ans = [1, 2, 3, ..., n+2]
wheren
is the length of strings
. This gives usn+1
numbers total, which is what we need for a permutation described by a string of lengthn
. -
Scan for consecutive 'D' segments: Use two pointers
i
andj
to identify segments of consecutive 'D' characters:- Start with
i = 0
to begin scanning from the first character - When we encounter a 'D' at position
i
, extendj
to find all consecutive 'D's - The inner while loop
while j < n and s[j] == 'D': j += 1
finds the end of the current 'D' segment
- Start with
-
Reverse the corresponding segment: When we find a segment of 'D's from index
i
toj-1
, we need to reverse the elements inans
from indexi
toj
(inclusive):ans[i : j + 1] = ans[i : j + 1][::-1]
reverses the slice- Note that we include position
j+1
in the reversal because we need one more number than the number of 'D's to create a decreasing sequence
-
Move to the next unprocessed position: After processing a segment:
- If we just reversed a segment, jump to position
j
(skip the processed 'D's) - Otherwise, move to
i + 1
to check the next character - This is handled by
i = max(i + 1, j)
- If we just reversed a segment, jump to position
Example walkthrough with s = "IDDI"
:
- Initial:
ans = [1, 2, 3, 4, 5]
- Position 0: 'I' - no change needed, move to position 1
- Position 1-2: "DD" found - reverse
ans[1:4]
=[2, 3, 4]
→[4, 3, 2]
- Result:
ans = [1, 4, 3, 2, 5]
- Position 3: 'I' - no change needed
- Final:
[1, 4, 3, 2, 5]
The time complexity is O(n)
as each element is visited at most twice (once during scanning, once during reversal). The space complexity is O(n)
for storing the answer array.
Ready to land your dream job?
Unlock your dream job with a 5-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's trace through the algorithm with s = "DDID"
:
Initial Setup:
- String
s = "DDID"
has length 4, so we need a permutation of [1, 2, 3, 4, 5] - Start with
ans = [1, 2, 3, 4, 5]
- Begin scanning at
i = 0
Step 1: Process first segment of D's
- At
i = 0
: we see 'D' - Use
j = 0
to find consecutive D's - Extend
j
:s[0] = 'D'
, soj = 1
- Extend
j
:s[1] = 'D'
, soj = 2
- Extend
j
:s[2] = 'I'
, stop atj = 2
- We found "DD" from index 0 to 1
- Reverse
ans[0:3]
(positions 0, 1, 2):[1, 2, 3]
becomes[3, 2, 1]
- Now
ans = [3, 2, 1, 4, 5]
- Move
i
to position 2
Step 2: Process 'I' at position 2
- At
i = 2
: we see 'I' - No reversal needed (3 < 4 already satisfied)
- Move
i
to position 3
Step 3: Process 'D' at position 3
- At
i = 3
: we see 'D' - Use
j = 3
to find consecutive D's - Extend
j
:j = 4
(reached end of string) - We found single "D" at index 3
- Reverse
ans[3:5]
(positions 3, 4):[4, 5]
becomes[5, 4]
- Now
ans = [3, 2, 1, 5, 4]
- Move
i
to position 4 (end of string)
Final Result: [3, 2, 1, 5, 4]
Verification:
- Position 0-1:
3 > 2
✓ (D satisfied) - Position 1-2:
2 > 1
✓ (D satisfied) - Position 2-3:
1 < 5
✓ (I satisfied) - Position 3-4:
5 > 4
✓ (D satisfied)
This is the lexicographically smallest permutation that satisfies the pattern "DDID".
Solution Implementation
1from typing import List
2
3class Solution:
4 def findPermutation(self, s: str) -> List[int]:
5 """
6 Constructs the lexicographically smallest permutation based on pattern string.
7
8 Args:
9 s: Pattern string containing 'I' (increase) and 'D' (decrease)
10
11 Returns:
12 List of integers representing the smallest valid permutation
13 """
14 # Length of the pattern string
15 n = len(s)
16
17 # Initialize result with ascending sequence [1, 2, 3, ..., n+1]
18 # We need n+1 numbers for n comparisons
19 result = list(range(1, n + 2))
20
21 # Process the pattern string
22 i = 0
23 while i < n:
24 # Find consecutive 'D' characters starting from position i
25 j = i
26 while j < n and s[j] == 'D':
27 j += 1
28
29 # Reverse the segment [i, j] in the result array
30 # This handles the decreasing subsequence requirement
31 result[i : j + 1] = result[i : j + 1][::-1]
32
33 # Move to the next unprocessed position
34 # Use max to handle both single character and consecutive 'D' cases
35 i = max(i + 1, j)
36
37 return result
38
1class Solution {
2 /**
3 * Finds the lexicographically smallest permutation based on the given pattern string.
4 * 'D' means the next number should be smaller (decreasing).
5 * 'I' means the next number should be larger (increasing).
6 *
7 * @param s The pattern string containing 'D' and 'I' characters
8 * @return The lexicographically smallest permutation array
9 */
10 public int[] findPermutation(String s) {
11 int patternLength = s.length();
12 int[] result = new int[patternLength + 1];
13
14 // Initialize the result array with values from 1 to n+1
15 for (int i = 0; i < patternLength + 1; i++) {
16 result[i] = i + 1;
17 }
18
19 int currentIndex = 0;
20
21 // Process the pattern string to handle consecutive 'D's
22 while (currentIndex < patternLength) {
23 int endIndex = currentIndex;
24
25 // Find the end of consecutive 'D's
26 while (endIndex < patternLength && s.charAt(endIndex) == 'D') {
27 endIndex++;
28 }
29
30 // Reverse the segment from currentIndex to endIndex to handle decreasing pattern
31 reverse(result, currentIndex, endIndex);
32
33 // Move to the next unprocessed position
34 currentIndex = Math.max(currentIndex + 1, endIndex);
35 }
36
37 return result;
38 }
39
40 /**
41 * Reverses a portion of the array from startIndex to endIndex (inclusive).
42 *
43 * @param arr The array to be partially reversed
44 * @param startIndex The starting index of the reversal
45 * @param endIndex The ending index of the reversal
46 */
47 private void reverse(int[] arr, int startIndex, int endIndex) {
48 while (startIndex < endIndex) {
49 // Swap elements at startIndex and endIndex
50 int temp = arr[startIndex];
51 arr[startIndex] = arr[endIndex];
52 arr[endIndex] = temp;
53
54 // Move pointers towards the center
55 startIndex++;
56 endIndex--;
57 }
58 }
59}
60
1class Solution {
2public:
3 vector<int> findPermutation(string s) {
4 int n = s.size();
5
6 // Initialize result array with values from 1 to n+1
7 // This represents the smallest lexicographic permutation initially
8 vector<int> result(n + 1);
9 iota(result.begin(), result.end(), 1);
10
11 int i = 0;
12
13 // Process the pattern string
14 while (i < n) {
15 // Find the start of a sequence of 'D's
16 int j = i;
17
18 // Extend j to include all consecutive 'D's
19 while (j < n && s[j] == 'D') {
20 ++j;
21 }
22
23 // Reverse the segment from index i to j (inclusive)
24 // This handles the decreasing requirement for 'D' characters
25 // For example, if we have "DD", we reverse [1,2,3] to get [3,2,1]
26 reverse(result.begin() + i, result.begin() + j + 1);
27
28 // Move to the next unprocessed position
29 // Use max to ensure we move forward even if no 'D's were found
30 i = max(i + 1, j);
31 }
32
33 return result;
34 }
35};
36
1function findPermutation(s: string): number[] {
2 const n: number = s.length;
3
4 // Initialize result array with values from 1 to n+1
5 // This represents the smallest lexicographic permutation initially
6 const result: number[] = Array.from({ length: n + 1 }, (_, index) => index + 1);
7
8 let i: number = 0;
9
10 // Process the pattern string
11 while (i < n) {
12 // Find the start of a sequence of 'D's
13 let j: number = i;
14
15 // Extend j to include all consecutive 'D's
16 while (j < n && s[j] === 'D') {
17 j++;
18 }
19
20 // Reverse the segment from index i to j (inclusive)
21 // This handles the decreasing requirement for 'D' characters
22 // For example, if we have "DD", we reverse [1,2,3] to get [3,2,1]
23 reverseArray(result, i, j + 1);
24
25 // Move to the next unprocessed position
26 // Use Math.max to ensure we move forward even if no 'D's were found
27 i = Math.max(i + 1, j);
28 }
29
30 return result;
31}
32
33// Helper function to reverse a portion of an array in-place
34function reverseArray(arr: number[], start: number, end: number): void {
35 // Reverse elements from start index to end index (exclusive)
36 while (start < end - 1) {
37 const temp: number = arr[start];
38 arr[start] = arr[end - 1];
39 arr[end - 1] = temp;
40 start++;
41 end--;
42 }
43}
44
Time and Space Complexity
Time Complexity: O(n)
The algorithm iterates through the string s
of length n
using a while loop with pointer i
. In each iteration:
- When we encounter a 'D', we find all consecutive 'D's using pointer
j
, which moves forward - We then reverse the subarray
ans[i : j + 1]
, which takesO(j - i + 1)
time - The pointer
i
is then moved to eitheri + 1
orj
, ensuring we don't revisit the same positions
Since each character in the string is visited at most twice (once by pointer i
and once by pointer j
), and each element in the answer array is involved in at most one reversal operation, the total time complexity is O(n)
.
Space Complexity: O(n)
The algorithm uses:
ans
: a list of sizen + 1
to store the result, requiringO(n)
space- The slice operation
ans[i : j + 1][::-1]
creates a temporary reversed copy of the subarray, which in the worst case (when all characters are 'D') could be of sizeO(n)
- Variables
i
,j
, andn
useO(1)
space
Therefore, the total space complexity is O(n)
.
Common Pitfalls
1. Off-by-One Error in Array Initialization
A common mistake is initializing the result array with incorrect size. Since we need n+1 numbers for a pattern string of length n (to have n comparisons), developers often mistakenly create an array of size n.
Incorrect:
result = list(range(1, n + 1)) # Creates [1, 2, ..., n] - Missing one element!
Correct:
result = list(range(1, n + 2)) # Creates [1, 2, ..., n+1]
2. Incorrect Segment Reversal Bounds
When reversing segments for consecutive 'D's, it's crucial to include the correct elements. The reversal should include one more element than the number of 'D's.
Incorrect:
# Only reversing elements corresponding to 'D' positions result[i:j] = result[i:j][::-1] # Missing the last element needed for decreasing sequence
Correct:
# Include position j to properly handle the decreasing constraint result[i:j+1] = result[i:j+1][::-1]
3. Improper Pointer Movement
After processing a segment of 'D's, failing to skip past the processed characters can lead to unnecessary operations or incorrect results.
Incorrect:
i += 1 # Always incrementing by 1, even after processing multiple 'D's
Correct:
i = max(i + 1, j) # Skip to position j after processing consecutive 'D's
4. Not Handling Edge Cases
Failing to handle strings consisting entirely of one character type ('IIII' or 'DDDD') can cause issues if the logic assumes mixed patterns.
Solution: The current implementation handles these cases naturally through the while loop structure, but developers might overcomplicate by adding unnecessary special case handling.
5. Confusion Between Index and Value
When working with permutations, it's easy to confuse array indices (0-based) with permutation values (1-based).
Example of confusion:
- Pattern string index: 0 to n-1
- Result array index: 0 to n
- Permutation values: 1 to n+1
Best Practice: Keep clear mental separation between positions in the pattern string, positions in the result array, and the actual values being permuted.
Which of the following is a min heap?
Recommended Readings
Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way
Want a Structured Path to Master System Design Too? Don’t Miss This!