Domain 1EasyCORE

DI String Match

The problem requires us to generate a permutation of integers from `0` to `n` based on a given string `s` of length `n`. The string `s` consists of characters `'I'` and `'D'`, where: - `'I'` indicates that the next number in the permutation should be greater than the current one. - `'D'` indicates that the next number in the permutation should be less than the current one.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Math

942. DI String Match

Model: qwen2.5-coder:14b
Topics: Math
FAANG asked: 0
Acceptance rate: 73.7%


Problem Breakdown

The problem requires us to generate a permutation of integers from 0 to n based on a given string s of length n. The string s consists of characters 'I' and 'D', where:

  • 'I' indicates that the next number in the permutation should be greater than the current one.
  • 'D' indicates that the next number in the permutation should be less than the current one.

Inputs:

  • A string s of length n containing only characters 'I' and 'D'.

Outputs:

  • An array of integers representing a valid permutation of numbers from 0 to n.

Implicit Constraints or Edge Cases:

  • The input string s will always be non-empty.
  • The output permutation must use all integers from 0 to n exactly once.

Intuition

A brute-force approach would involve generating all permutations and checking each one against the conditions specified by the string s. However, this is computationally expensive with a time complexity of O(n!), which is infeasible for large values of n.

The key insight is to use two pointers or counters to keep track of the smallest and largest numbers available. When encountering an 'I', we take the smallest number (to ensure the next number can be larger), and when encountering a 'D', we take the largest number (to ensure the next number can be smaller). This approach ensures that we always satisfy the conditions specified by s while using all numbers from 0 to n.

Approach

  1. Initialize two pointers: low starting at 0 and high starting at n.
  2. Iterate through each character in the string s:
    • If the character is 'I', append low to the result list and increment low.
    • If the character is 'D', append high to the result list and decrement high.
  3. After processing all characters, one number will remain (either low or high), which should be appended to the result list.

This approach ensures that we generate a valid permutation with linear time complexity.

Complexity Analysis

  • Time Complexity: O(n) - We iterate through the string s once.
  • Space Complexity: O(n) - We store the resulting permutation in a list of length n.

Solution

def diStringMatch(s: str) -> List[int]:
    low, high = 0, len(s)
    result = []
    
    for char in s:
        if char == 'I':
            result.append(low)
            low += 1
        else:
            result.append(high)
            high -= 1
    
    # Append the last remaining number
    result.append(low)  # or result.append(high), since low should equal high at this point
    
    return result

Edge Cases Handled

  • All ‘I’: The code correctly handles strings like “III” by always appending the smallest available number, resulting in a strictly increasing sequence.
  • All ‘D’: The code correctly handles strings like “DDD” by always appending the largest available number, resulting in a strictly decreasing sequence.
  • Mixed ‘I’ and ‘D’: The code correctly alternates between the smallest and largest numbers based on the input string, ensuring the permutation satisfies all conditions.