#942

Easy

auto_awesomeTwo-pointer scanning with invariant tracking

LeetCode Problem Workspace

DI String Match

Reconstruct a permutation from a DI string using two-pointer scanning, carefully tracking the increasing and decreasing invariants.

array two pointers string greedy

Problem Statement

You are given a string s of length n consisting only of 'I' (increase) and 'D' (decrease). Construct a permutation perm of length n+1 containing all integers from 0 to n such that for each index i, if s[i] is 'I', then perm[i] < perm[i+1], and if s[i] is 'D', then perm[i] > perm[i+1]. Return any valid permutation that satisfies these conditions.

For example, given s = "IDID", a valid output is [0,4,1,3,2]. Your task is to implement a solution that efficiently assigns numbers while maintaining the two-pointer invariant to satisfy the pattern of increasing and decreasing segments. Constraints: 1 <= s.length <= 10^5, and s[i] is either 'I' or 'D'.

Examples

Example 1

Input: s = "IDID"

Output: [0,4,1,3,2]

Example details omitted.

Example 2

Input: s = "III"

Output: [0,1,2,3]

Example details omitted.

Example 3

Input: s = "DDI"

Output: [3,2,0,1]

Example details omitted.

Constraints

1 <= s.length <= 105
s[i] is either 'I' or 'D'.

Solution Approach

Initialize two pointers

Set a low pointer at 0 and a high pointer at n. These represent the smallest and largest numbers available to assign to the permutation as you scan the string s.

Scan string and assign numbers

Iterate through each character in s: if it is 'I', assign the number at the low pointer and increment low; if it is 'D', assign the number at the high pointer and decrement high. This ensures each position respects the increasing or decreasing requirement.

Finalize permutation

After processing all characters, assign the remaining number (low and high converge) to the last position. This completes a valid permutation satisfying the DI string pattern with O(N) time and O(1) extra space.

Complexity Analysis

Metric	Value
Time	O(N)
Space	O(1)

Time complexity is O(N) because each character is processed once in a single pass. Space complexity is O(1) beyond the output array, as only two pointers are maintained.

What Interviewers Usually Probe

Pay attention to off-by-one errors when assigning low and high pointers.
Clarify that multiple valid permutations exist and returning any is acceptable.
Explain how the two-pointer invariant guarantees all 'I' and 'D' constraints are satisfied.

Common Pitfalls or Variants

Common pitfalls

Swapping low and high pointers incorrectly leading to invalid permutations.
Failing to handle the final element after the loop, leaving it unassigned.
Misinterpreting 'I' and 'D' conditions, producing reversed relationships.

Follow-up variants

Return all valid permutations instead of any single one.
Handle strings with additional characters representing equality or custom ordering.
Solve in-place if the input array representation is given instead of a string.

FAQ

What is the easiest approach to solve DI String Match?

Use a two-pointer scanning method: assign the smallest remaining number for 'I' and the largest for 'D', ensuring the pattern holds.

Can multiple valid permutations exist for the same DI string?

Yes, different sequences of number assignments can satisfy the 'I' and 'D' conditions, but any single valid permutation is acceptable.

What is the time complexity of the two-pointer solution?

The algorithm runs in O(N) time, processing each character of the string once, with O(1) additional space for pointers.

How do I handle large input sizes efficiently?

Maintain just the low and high pointers without extra data structures; this ensures linear time and minimal space usage.

Why is the pattern called 'Two-pointer scanning with invariant tracking'?

Because it scans the string with two pointers representing the smallest and largest available numbers, maintaining the invariant that all assigned numbers satisfy the 'I' and 'D' rules.

terminal

Solution

Solution 1: Greedy Algorithm

We can use two pointers `low` and `high` to represent the current minimum and maximum values, respectively. Then, we traverse the string `s`. If the current character is `I`, we add `low` to the result array, and increment `low` by 1; if the current character is `D`, we add `high` to the result array, and decrement `high` by 1.

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def diStringMatch(self, s: str) -> List[int]:
        low, high = 0, len(s)
        ans = []
        for c in s:
            if c == "I":
                ans.append(low)
                low += 1
            else:
                ans.append(high)
                high -= 1
        ans.append(low)
        return ans

Continue Practicing

#948 bag of tokens #969 pancake sorting #881 boats to save people