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
sof lengthncontaining only characters'I'and'D'.
Outputs:
- An array of integers representing a valid permutation of numbers from
0ton.
Implicit Constraints or Edge Cases:
- The input string
swill always be non-empty. - The output permutation must use all integers from
0tonexactly 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
- Initialize two pointers:
lowstarting at0andhighstarting atn. - Iterate through each character in the string
s:- If the character is
'I', appendlowto the result list and incrementlow. - If the character is
'D', appendhighto the result list and decrementhigh.
- If the character is
- After processing all characters, one number will remain (either
loworhigh), 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
sonce. - 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.