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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

DI String Match

Number: 979

Difficulty: Easy

Paid? No

Companies: Google, Bloomberg

Problem Description

Given a string s consisting of characters 'I' and 'D', where each character represents an increasing or decreasing relationship between consecutive elements of a permutation, construct a permutation perm of n+1 integers (from 0 to n) such that:

  • If s[i] == 'I', then perm[i] < perm[i+1].
  • If s[i] == 'D', then perm[i] > perm[i+1].

Return any valid permutation that meets these criteria.

Key Insights

  • The pattern string of length n defines relationships for n+1 numbers.
  • Use a two-pointer approach: one pointer (low) starting at 0 and another (high) starting at n.
  • For each character in s:
    • If the character is 'I' (increase), assign the current position the value low and then increment low.
    • If the character is 'D' (decrease), assign the current position the value high and then decrement high.
  • After processing all characters, assign the final remaining number to complete the permutation.

Space and Time Complexity

Time Complexity: O(n) - Single pass through the string. Space Complexity: O(n) - Storage for the resulting permutation.

Solution

This problem is solved using a greedy approach with two pointers. Initialize two indices: low = 0 and high = length of s (which is n). Iterate over the string s:

  • For each 'I' character, take the smallest available number (low) and output it, then increment low.
  • For each 'D' character, take the largest available number (high) and output it, then decrement high. At the end of the iteration, only one number will be left (since the permutation contains n+1 numbers); output that remaining number. Key data structures used include:
  • An array (or list) to store the permutation results.
  • Two integer pointers to track the next minimum and maximum value available. This approach works because it greedily assigns numbers in a way that respects the increasing or decreasing constraint at each step.

Code Solutions

# Python solution for DI String Match
def diStringMatch(s):
    # Initialize the result list and the two pointers
    n = len(s)
    result = []
    low, high = 0, n

    # Iterate over each character in the string
    for char in s:
        # If the character is 'I', append the lowest available number
        if char == 'I':
            result.append(low)
            low += 1
        else:  # char == 'D'
            result.append(high)
            high -= 1

    # Append the last remaining number
    result.append(low)
    return result

# Example usage:
print(diStringMatch("IDID"))
← Back to All Questions