484. Find Permutation - Explanation

Description

A permutation perm of n integers of all the integers in the range [1, n] can be represented as a string s of length n - 1 where:

s[i] == 'I' if perm[i] < perm[i + 1], and
s[i] == 'D' if perm[i] > perm[i + 1].

Given a string s, reconstruct the lexicographically smallest permutation perm and return it.

Example 1:

Input: s = "I"

Output: [1,2]

Explanation: [1,2] is the only legal permutation that can represented by s, where the number 1 and 2 construct an increasing relationship.

Example 2:

Input: s = "DI"

Output: [2,1,3]

Explanation: Both [2,1,3] and [3,1,2] can be represented as "DI", but since we want to find the smallest lexicographical permutation, you should return [2,1,3]

Constraints:

1 <= s.length <= 10⁵
s[i] is either 'I' or 'D'.

Company Tags

Google2

1. Using Stack

class Solution:
    def findPermutation(self, s: str) -> List[int]:
        res = [0] * (len(s) + 1)
        stack = []
        j = 0

        for i in range(1, len(s) + 1):
            if s[i - 1] == 'I':
                stack.append(i)
                while stack:
                    res[j] = stack.pop()
                    j += 1
            else:
                stack.append(i)

        stack.append(len(s) + 1)
        while stack:
            res[j] = stack.pop()
            j += 1

        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

Where $n$ is the number of elements in the resultant arrangement

2. Reversing the subarray

class Solution:
    def findPermutation(self, s: str) -> List[int]:
        n = len(s)
        res = [i + 1 for i in range(n + 1)]

        i = 1

        while i <= n:
            j = i

            while i <= n and s[i - 1] == 'D':
                i += 1

            self.reverse(res, j - 1, i)
            i += 1

        return res

    def reverse(self, a: List[int], start: int, end: int) -> None:
        for i in range((end - start) // 2):
            temp = a[i + start]
            a[i + start] = a[end - i - 1]
            a[end - i - 1] = temp

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

Where $n$ is the size of the resultant array

3. Two pointers

class Solution:
    def findPermutation(self, s: str) -> List[int]:
        n = len(s)
        res = [0] * (n + 1)
        res[0] = 1
        i = 1

        while i <= n:
            res[i] = i + 1
            j = i

            if s[i - 1] == 'D':
                while i <= n and s[i - 1] == 'D':
                    i += 1

                k, c = j - 1, i
                while k <= i - 1:
                    res[k] = c
                    k += 1
                    c -= 1
            else:
                i += 1

        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

Where $n$ is the size of the resultant array