Facebook Pixel

484. Find Permutation 🔒

MediumStackGreedyArrayString
Leetcode Link

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' means perm[i] < perm[i+1] (increasing)
  • s[i] = 'D' means perm[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.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

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:

  1. We only disturb the natural ascending order where absolutely necessary (at 'D' positions)
  2. By reversing consecutive 'D' segments, we use the smallest possible numbers that can satisfy the decreasing constraint
  3. 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:

  1. Initialize the base permutation: Start with ans = [1, 2, 3, ..., n+2] where n is the length of string s. This gives us n+1 numbers total, which is what we need for a permutation described by a string of length n.

  2. Scan for consecutive 'D' segments: Use two pointers i and j 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, extend j 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

  3. Reverse the corresponding segment: When we find a segment of 'D's from index i to j-1, we need to reverse the elements in ans from index i to j (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

  4. 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)

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 Evaluator

Example 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', so j = 1
  • Extend j: s[1] = 'D', so j = 2
  • Extend j: s[2] = 'I', stop at j = 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 takes O(j - i + 1) time
  • The pointer i is then moved to either i + 1 or j, 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 size n + 1 to store the result, requiring O(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 size O(n)
  • Variables i, j, and n use O(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.

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

Which algorithm is best for finding the shortest distance between two points in an unweighted graph?

Recommended Readings

Stack Intro

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

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: The Smart, Data-Driven Way to Prepare for Tech Interviews

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!

Load More