Leetcode – DI String Match Solution in Python

Spread the love

This article offers an in-depth exploration of the DI String Match problem, provides a methodical approach, and concludes with a Python solution.

Problem Statement

Given a string S that only contains “I” (increase) or “D” (decrease), let N = S.length. Return any permutation A of [0, 1, ..., N] such that for all i = 0, ..., N-1:

  • If S[i] == "I", then A[i] < A[i+1]
  • If S[i] == "D", then A[i] > A[i+1]

Understanding the Problem

The problem’s crux is to generate an array of integers that satisfy the conditions provided by the input string. Every “I” in the string dictates that the next number in the array should be greater, while a “D” suggests the next number should be smaller.

Key Insight

A clever way to tackle this problem is to approach it with two pointers or counters. By maintaining the smallest and largest values available from the set [0, 1, ..., N], we can efficiently satisfy the increasing and decreasing conditions. For every “I”, use the smallest available number, and for every “D”, use the largest available number.

Algorithm to Solve the Problem

  1. Initialize two counters, low and high, with values 0 and N respectively.
  2. Create an empty result list res.
  3. Traverse the string S:
    • For every “I”, append low to res and increment low.
    • For every “D”, append high to res and decrement high.
  4. After processing all characters of S, append low (or high, as they will be the same) to res.
  5. Return res.

Python Code Solution

Here’s how you can implement the solution in Python:

def diStringMatch(S):
    low, high = 0, len(S)
    res = []
    for char in S:
        if char == "I":
            res.append(low)
            low += 1
        else:
            res.append(high)
            high -= 1
    res.append(low)  # or res.append(high) would work as well
    return res

Complexity Analysis

  • Time Complexity: O(N) – The algorithm traverses the string S once, where N is the length of the string.
  • Space Complexity: O(N) – The solution creates a list res that contains N + 1 integers.

Testing the Solution

Testing is an integral phase in the problem-solving cycle. Let’s validate our solution:

print(diStringMatch("IDID"))       # Expected output: [0, 4, 1, 3, 2] (among other valid solutions)
print(diStringMatch("III"))        # Expected output: [0, 1, 2, 3]
print(diStringMatch("DDI"))        # Expected output: [3, 2, 1, 0] (among other valid solutions)

Conclusion

The “DI String Match” problem encapsulates the importance of intuition and insight in algorithmic challenges. While the problem may initially appear complex, a methodical breakdown and the application of basic pointers make the solution both elegant and efficient. As we journey through such problems, it becomes evident that sometimes the simplest strategies, like the two-pointer approach in this case, can unravel seemingly intricate challenges.

Leave a Reply