Is DI String Match easy or hard?

DI String Match is classified as an Easy problem on LeetCode with a high acceptance rate around 80%. The main challenge is recognizing the greedy pattern where using the smallest or largest available number preserves valid options for the remaining positions.

DI String Match Python/Java solution

Python and Java implementations follow the same logic: initialize low = 0 and high = n, iterate through the string, append low for 'I' or high for 'D', then update the pointer. After the loop, append the remaining value. The implementation runs in O(n) time with constant extra space.

How to solve DI String Match in O(n)?

Track the smallest and largest unused numbers using two pointers. Iterate through the string: if the character is 'I', append the current low value and increase it; if it is 'D', append the current high value and decrease it. After processing all characters, append the remaining number. This single pass guarantees O(n) time.

What is the best approach for DI String Match?

The optimal approach uses a greedy two-pointer strategy. Maintain two values, low = 0 and high = n, representing the smallest and largest unused numbers. For 'I', assign low and increment it; for 'D', assign high and decrement it. This guarantees each constraint is satisfied while scanning the string once.

Is DI String Match asked at Google/Amazon/Meta?

Problems based on greedy permutation construction and two-pointer reasoning appear frequently in technical interviews at companies like Amazon, Google, and Meta. DI String Match is considered an entry-level greedy problem used to test algorithmic thinking and pattern recognition.

What data structure is used in DI String Match?

The solution mainly uses an array (or list) to build the resulting permutation. Two integer pointers track the remaining range of available numbers. No advanced data structures such as heaps or hash maps are required.

What is the time complexity of DI String Match?

The optimal solution runs in O(n) time because the algorithm iterates through the string exactly once and performs constant-time operations per character. Space complexity is O(1) excluding the output array since only two pointer variables are maintained.

Description Solution Video 6:33

942. DI String Match

Easy81.0% acceptance3 companies

A permutation perm of n + 1 integers of all the integers in the range [0, n] can be represented as a string s of length n where:

s[i] == 'I' if perm[i] < perm[i + 1], and
s[i] == 'D' if perm[i] > perm[i + 1].

Given a string s, reconstruct the permutation perm and return it. If there are multiple valid permutations perm, return any of them.

Example 1:

Input: s = "IDID"
Output: [0,4,1,3,2]

Example 2:

Input: s = "III"
Output: [0,1,2,3]

Example 3:

Input: s = "DDI"
Output: [3,2,0,1]

Constraints:

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

Asked at 3 companies

Google Amazon Bloomberg

Topics

6:33

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

942. DI String Match

Asked at 3 companies

Topics

Similar problems