{x}
blog image

DI String Match

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 <= 105
  • s[i] is either 'I' or 'D'.

Solution Explanation for DI String Match

The problem asks to reconstruct a permutation perm of numbers from 0 to n, given a string s of length n. The string s indicates the relationship between consecutive elements in perm: 'I' means the next element is greater, and 'D' means it's smaller. The solution needs to return one possible permutation that satisfies the conditions.

Approach: Greedy Algorithm

The most efficient approach is a greedy algorithm. We maintain two pointers, low and high, initialized to 0 and n respectively. We iterate through the input string s.

  • If s[i] is 'I' (increasing): This means perm[i] should be the smallest available number. We append low to the result, and increment low.

  • If s[i] is 'D' (decreasing): This means perm[i] should be the largest available number. We append high to the result, and decrement high.

After iterating through the entire string, the remaining value at low is the last element of the permutation.

Time and Space Complexity

  • Time Complexity: O(n), where n is the length of the input string s. We iterate through the string once.

  • Space Complexity: O(n). We store the resulting permutation in an array of size n+1.

Code Implementation in Multiple Languages

The following code snippets demonstrate the implementation of this greedy algorithm in various programming languages:

Python

def diStringMatch(s):
    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)  #Append the remaining low value
    return ans

Java

class Solution {
    public int[] diStringMatch(String s) {
        int low = 0, high = s.length();
        int[] ans = new int[s.length() + 1];
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == 'I') {
                ans[i] = low++;
            } else {
                ans[i] = high--;
            }
        }
        ans[s.length()] = low; //Append the remaining low value
        return ans;
    }
}

C++

vector<int> diStringMatch(string s) {
    int low = 0, high = s.length();
    vector<int> ans(s.length() + 1);
    for (int i = 0; i < s.length(); ++i) {
        if (s[i] == 'I') {
            ans[i] = low++;
        } else {
            ans[i] = high--;
        }
    }
    ans[s.length()] = low; //Append the remaining low value
    return ans;
}

JavaScript

const diStringMatch = (s) => {
    let low = 0, high = s.length;
    const ans = [];
    for (let i = 0; i < s.length; i++) {
        if (s[i] === 'I') {
            ans.push(low++);
        } else {
            ans.push(high--);
        }
    }
    ans.push(low); //Append the remaining low value
    return ans;
};

Go

func diStringMatch(s string) []int {
    low, high := 0, len(s)
    ans := make([]int, len(s)+1)
    for i := range s {
        if s[i] == 'I' {
            ans[i] = low
            low++
        } else {
            ans[i] = high
            high--
        }
    }
    ans[len(s)] = low //Append the remaining low value
    return ans
}

These examples all follow the same greedy strategy, demonstrating its adaptability across different programming languages. The key is efficiently using low and high to build the permutation based on the increasing ('I') or decreasing ('D') instructions from the input string.