We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find Permutation

Number: 484

Difficulty: Medium

Paid? Yes

Companies: Google

Problem Description

Given a string s composed only of the characters 'I' (for increasing) and 'D' (for decreasing), we need to reconstruct the lexicographically smallest permutation of the first n integers (where n = s.length + 1) such that:

  • For every index i in s, if s[i] is 'I', then perm[i] < perm[i+1], and if s[i] is 'D', then perm[i] > perm[i+1].

Key Insights

  • The answer is a permutation of numbers from 1 to n, where n = len(s) + 1.
  • A common strategy is to use a stack to reverse the segments when a decrease ('D') is encountered.
  • When an 'I' is encountered (or at the end), pop all numbers from the stack to output them in reverse order, ensuring the smallest lexicographical order.
  • This greedy approach guarantees that as soon as a rising pattern is detected, we “flush” the pending decreases correctly.

Space and Time Complexity

Time Complexity: O(n) – Each element is pushed and popped exactly once. Space Complexity: O(n) – For the stack and the output array.

Solution

We use a greedy approach with a stack. Iterate from 0 to n (where n = len(s) + 1):

  1. Push the current number (i+1) onto the stack.
  2. If the current character is 'I' or we have reached the end of the string, pop all elements from the stack and append them to the result. By doing so, segments corresponding to series of 'D's are reversed, while 'I's trigger the flush, ensuring that the final permutation is the lexicographically smallest.

Code Solutions

# Function to find the lexicographically smallest permutation
def findPermutation(s):
    stack = []  # Use a stack to hold numbers during a sequence of 'D's
    result = [] # Result list for the final permutation
    # Iterate over 0 to len(s) (inclusive) to process all characters plus one final number.
    for i in range(len(s) + 1):
        # Push i+1 since our numbers range from 1 to n
        stack.append(i + 1)
        # If we are at the end or the current character is 'I', flush the stack.
        if i == len(s) or s[i] == 'I':
            while stack:
                result.append(stack.pop())
    return result

# Example usage:
print(findPermutation("DI"))
← Back to All Questions