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

DI String Match

Difficulty: Easy

Problem Description

Given a string s consisting of characters 'I' (increasing) and 'D' (decreasing), reconstruct a permutation perm of n + 1 integers in the range [0, n] such that perm[i] < perm[i + 1] for each occurrence of 'I' and perm[i] > perm[i + 1] for each occurrence of 'D'. If there are multiple valid permutations, return any of them.

Key Insights

  • The string s determines the relative ordering of the integers in the permutation.
  • 'I' indicates an increase, meaning the next number must be greater than the current one.
  • 'D' indicates a decrease, meaning the next number must be less than the current one.
  • A greedy approach can be used to assign numbers based on the pattern in the string.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve the problem, we can use a greedy approach where we maintain two pointers: one starting from the beginning and the other from the end of the possible number range. We traverse the string s and fill the permutation array based on whether we encounter 'I' or 'D'. For 'I', we append the next lowest number from the beginning, and for 'D', we append the next highest number from the end. This ensures that the constraints of the permutation are met.

Code Solutions

def di_string_match(s: str) -> List[int]:
    n = len(s)
    perm = []
    low, high = 0, n
    
    for char in s:
        if char == 'I':
            perm.append(low)
            low += 1
        else:  # char == 'D'
            perm.append(high)
            high -= 1
            
    perm.append(low)  # Append the last number
    return perm
← Back to All Questions