Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/484.html
484. Find Permutation
Level
Medium
Description
By now, you are given a secret signature consisting of character ‘D’ and ‘I’. ‘D’ represents a decreasing relationship between two numbers, ‘I’ represents an increasing relationship between two numbers. And our secret signature was constructed by a special integer array, which contains uniquely all the different number from 1 to n (n is the length of the secret signature plus 1). For example, the secret signature “DI” can be constructed by array [2,1,3] or [3,1,2], but won’t be constructed by array [3,2,4] or [2,1,3,4], which are both illegal constructing special string that can’t represent the “DI” secret signature.
On the other hand, now your job is to find the lexicographically smallest permutation of [1, 2, … n] could refer to the given secret signature in the input.
Example 1:
Input: “I”
Output: [1,2]
Explanation: [1,2] is the only legal initial spectial string can construct secret signature “I”, where the number 1 and 2 construct an increasing relationship.
Example 2:
Input: “DI”
Output: [2,1,3]
Explanation: Both [2,1,3] and [3,1,2] can construct the secret signature “DI”, but since we want to find the one with the smallest lexicographical permutation, you need to output [2,1,3].
Note:
- The input string will only contain the character ‘D’ and ‘I’.
- The length of input string is a positive integer and will not exceed 10,000
Solution
To obtain the lexicographically smallest permutation, always use the smallest possible integer at each index. If a “D” is met, count the maximum number of consecutive “D”s, and the numbers at such indices are permuted in descending order. Find the minimum possible number for the first “D”, and fill in all the indices with “D”. If an “I” is met, simply use the smallest number that is greater than the previous largest number.
-
class Solution { public int[] findPermutation(String s) { int length = s.length(); int[] permutation = new int[length + 1]; int curNum = 1; int startIndex = 0; int decreaseCount = 0; for (int i = 0; i < length; i++) { char c = s.charAt(i); if (c == 'D') decreaseCount++; else { if (decreaseCount == 0) { permutation[i] = curNum; curNum++; startIndex++; } else { int num = curNum + decreaseCount; curNum = num + 1; for (int j = startIndex; j <= i; j++) { permutation[j] = num; num--; } startIndex = i + 1; decreaseCount = 0; } } } if (decreaseCount == 0) permutation[length] = curNum; else { int num = curNum + decreaseCount; curNum = num + 1; for (int i = startIndex; i <= length; i++) { permutation[i] = num; num--; } } return permutation; } } -
class Solution: def findPermutation(self, s: str) -> List[int]: n = len(s) ans = list(range(1, n + 2)) i = 0 while i < n: j = i while j < n and s[j] == 'D': j += 1 ans[i : j + 1] = ans[i : j + 1][::-1] i = max(i + 1, j) return ans ############ class Solution(object): def findPermutation(self, s): """ :type s: str :rtype: List[int] """ ans = range(1, len(s) + 2) cnt = 0 for i in range(len(s)): if s[i] == "D": cnt += 1 else: ans[i - cnt:i + 1] = ans[i - cnt:i + 1][::-1] cnt = 0 if s[-1] == "D": ans[len(s) - cnt:len(s) + 1] = ans[len(s) - cnt:len(s) + 1][::-1] return ans -
class Solution { public: vector<int> findPermutation(string s) { int n = s.size(); vector<int> ans(n + 1); iota(ans.begin(), ans.end(), 1); int i = 0; while (i < n) { int j = i; while (j < n && s[j] == 'D') { ++j; } reverse(ans.begin() + i, ans.begin() + j + 1); i = max(i + 1, j); } return ans; } }; -
func findPermutation(s string) []int { n := len(s) ans := make([]int, n+1) for i := range ans { ans[i] = i + 1 } i := 0 for i < n { j := i for ; j < n && s[j] == 'D'; j++ { } reverse(ans, i, j) i = max(i+1, j) } return ans } func reverse(arr []int, i, j int) { for ; i < j; i, j = i+1, j-1 { arr[i], arr[j] = arr[j], arr[i] } } func max(a, b int) int { if a > b { return a } return b }