DI String Match

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]

Example 1:

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

Approach

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class DIStringMatch {
    public static void main(String[] args) {
        String str = "IDID";
        int[] DI = diStringMatch(str);
        System.out.println(Arrays.toString(DI));
    }

    static int[] diStringMatch(String S) {
        int l = 0, r = S.length();
        List<Integer> res = new ArrayList<Integer>();
        for (int i = 0; i < S.length(); i++) {
            if (S.charAt(i) == 'I')
                res.add(l++);
            else
                res.add(r--);
        }
        res.add(l);
        return res.stream().mapToInt(Integer::intValue).toArray();
    }

}

C++

#include <bits/stdc++.h>
using namespace std;

vector<int> diStringMatch(string S)
{
    int l = 0, r = S.size();
    vector<int> res;
    for (int i = 0; i < S.size(); i++)
    {
        if (S[i] == 'I')
            res.push_back(l++);
        else
            res.push_back(r--);
    }
    res.push_back(l);
    return res;
}

int main()
{
    string str = "IDID";
    vector<int> DI = diStringMatch(str);
    cout << "[";
    for (int i = 0; i < DI.size() - 1; i++)
        cout << DI[i] << ",";
    cout << DI[DI.size() - 1] << "]";
    return 0;
}