algoadvance

Leetcode 942. DI String Match

Problem Statement

You are given a string s that contains only the characters 'I' (for “increase”) and 'D' (for “decrease”). Let n be the length of the string s. The goal is to construct an array perm of length n + 1 where:

• The array perm contains all integers from 0 to n.
• For every i from 0 to n - 1:
  • If s[i] is 'I', then perm[i] < perm[i + 1].
  • If s[i] is 'D', then perm[i] > perm[i + 1].

You need to return one such array perm.

Example

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

Clarifying Questions

1. What should we return if the input string does not contain any characters or is empty?
   • Even if the string s is empty, we should return a single-element array [0].
2. Do we need to validate the input string to ensure it contains only ‘I’ and ‘D’ characters?
   • For the purpose of this problem, you can assume that the input string s is always valid and contains only ‘I’ and ‘D’.
3. Is the solution expected to work in-place or can we use additional memory?
   • We are allowed to use additional memory to achieve the desired solution.

Strategy

Approach

1. Two-pointer approach:
   • Initialize two pointers, low starting at 0 and high starting at n.
   • Iterate through each character in the string s.
   • If the character is ‘I’, add low to the result array and increment low.
   • If the character is ‘D’, add high to the result array and decrement high.
   • Finally, add the remaining value of low (or high, since they would be equal at this point) to the result array.

Time Complexity

• The solution will have a time complexity of O(n) since we are traversing the string s once, performing O(1) operations in each iteration.

Code

#include <vector>
#include <string>

std::vector<int> diStringMatch(const std::string& s) {
    int n = s.length();
    std::vector<int> perm(n + 1);
    int low = 0, high = n;

    for (int i = 0; i < n; ++i) {
        if (s[i] == 'I') {
            perm[i] = low++;
        } else {
            perm[i] = high--;
        }
    }
    perm[n] = low; // low and high should be the same at this point
    
    return perm;
}

Explanation of the Code

1. We initialize low to 0 and high to n.
2. We use a loop to iterate over each character in the string s.
3. Depending on whether the character is ‘I’ or ‘D’, we append low or high to the perm array and update the pointers.
4. Finally, we append the remaining number to the last position of perm.

This gives us the required permutation array that satisfies the conditions for ‘I’ and ‘D’.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?