Leetcode 484. Find Permutation

Problem Description

This problem requires you to find the lexicographically smallest permutation of the numbers [1, 2, ..., n] that can represent a secret signature. The secret signature is a string made of characters 'D' and 'I', where 'D' indicates that the next number in the sequence is smaller and 'I' indicates that the next number is larger. The number 'n' in this case is equal to the length of the secret signature plus 1.

Here are some examples to illustrate:

If the input is "I", we need to find a sequence of numbers that starts with a smaller number and then goes to a larger number. The only possible sequence is [1,2].

If the input is "DI", we need to find a sequence of numbers that starts with a smaller number, then goes to a larger number, and then back to a smaller number. The two possible sequences are [2,1,3] and [3,1,2]. However, we want to find the lexicographically smallest sequence, so the correct output is [2,1,3].

Solution Approach

This problem can be solved by using a stack data structure. A stack data structure follows the Last-In, First-Out (LIFO) principle.

In this case, for each character in the input string, we push a number (index + 1) into the stack. When we encounter a 'I', we pop all elements from the stack and append them to our answer list. After iterating through the string, we add the last number (length of the string + 1) and pop out all remaining stack elements into our answer list.

Python Solution

1
2python
3class Solution:
4    def findPermutation(self, s: str) -> List[int]:
5        ans = []
6        stack = []
7        
8        for i in range(len(s)):
9            stack.append(i + 1)
10            if s[i] == 'I':
11                while stack:
12                    ans.append(stack.pop())
13                    
14        # Append the last element
15        stack.append(len(s) + 1)
16        while stack:
17            ans.append(stack.pop())
18            
19        return ans

Java Solution

1
2java
3class Solution {
4    public int[] findPermutation(String s) {
5        int[] ans = new int[s.length() + 1];
6        Stack<Integer> stack = new Stack<>();
7        
8        int j = 0;
9        for (int i = 0; i <= s.length(); i++) {
10            stack.push(i + 1);
11            if (i == s.length() || s.charAt(i) == 'I') {
12                while (!stack.isEmpty())
13                    ans[j++] = stack.pop();
14            }
15        }
16        return ans;
17    }
18}

Javascript Solution

1
2javascript
3class Solution {
4    findPermutation(s) {
5        let ans = [];
6        let stack = [];
7        
8        for (let i = 0; i < s.length; i++) {
9            stack.push(i + 1);
10            if (s[i] == 'I') {
11                while (stack.length > 0)
12                    ans.push(stack.pop());
13            }
14        }
15        
16        // Append the last element
17        stack.push(s.length + 1);
18        while (stack.length > 0)
19            ans.push(stack.pop());
20        
21        return ans;
22    }
23}

C++ Solution

1
2cpp
3class Solution {
4public:
5    vector<int> findPermutation(string s) {
6        vector<int> ans;
7        stack<int> stack;
8        
9        for (int i = 0; i < s.length(); i++) {
10            stack.push(i + 1);
11            if (s[i] == 'I') {
12                while (!stack.empty()) {
13                    ans.push_back(stack.top());
14                    stack.pop();
15                }
16            }
17        }
18        
19        // Append the last element
20        stack.push(s.length() + 1);
21        while (!stack.empty()) {
22            ans.push_back(stack.top());
23            stack.pop();
24        }
25        
26        return ans;
27    }
28};

C# Solution

1
2csharp
3public class Solution {
4    public int[] FindPermutation(string s) {
5        int[] ans = new int[s.Length + 1];
6        Stack<int> stack = new Stack<int>();
7        
8        int j = 0;
9        for (int i = 0; i <= s.Length; i++) {
10            stack.Push(i + 1);
11            if (i == s.Length || s[i] == 'I') {
12                while (stack.Count > 0)
13                    ans[j++] = stack.Pop();
14            }
15        }
16        return ans;
17    }
18}

In all the solutions, we initialize a stack and a list to hold the final solution. For every character in the string, we push an index-related number to the stack. When we encounter an 'I', we pop all elements from the stack and append them to our solution list. In the end, we push the last number to the stack and pop out all remaining.## Final Words

Solving this problem involves understanding the properties of the stack data structure and the meaning of the input string characters. Once we understood that a 'D' in the input string makes the next number in the sequence smaller, and 'I' makes the next number larger, we could formulate a plan to solve the problem.

The provided Python, Java, JavaScript, C++ and C# solutions follow the same approach and use similar syntax for stack manipulation and list creation. They offer a concise and efficient way to solve this problem coded in multiple programming languages.

Understanding different data structures and the ways to manipulate them is a crucial aspect of problem-solving and programming in general. This exercise may be a useful resource for those learning about stack operations, sequence manipulation, or are preparing for coding interviews.

Whether you are a beginner eager to improve or a seasoned coder preparing for big tech companies’ interviews, keep practicing and learning. Coding is an iterative process, the more you practice, the more you get better at it. Happy coding!