Start by immediately assigning the smallest and largest available numbers at each step while scanning the string. For each 'I', pick the next smallest number, and for each 'D', pick the next largest. This two-pointer approach ensures that the resulting permutation satisfies all increasing and decreasing constraints in a single pass with O(N) time and constant extra space.
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.
How GhostInterview Helps
- Automatically tracks low and high pointers to guide number assignments in each step.
- Highlights off-by-one and invariant violations to prevent common two-pointer mistakes.
- Generates step-by-step explanations for why each number choice satisfies the DI pattern.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
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.
Need direct help with DI String Match instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture DI String Match from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Maximize your score in the Bag of Tokens problem by strategically playing tokens with two-pointer scanning and greedy techniques.
Open problem page#969 Pancake SortingSort an array using pancake flips, leveraging two-pointer scanning and invariant tracking to iteratively position the largest unsorted elements.
Open problem page#881 Boats to Save PeopleFind the minimum number of boats required to save all people, using a two-pointer approach for efficient pairing.
Open problem page