A totally different approach


#1

A different approach.

First represent I and D with +1 and -1 in arr. (1)
Then prefix sum the array. (2)
then find maximum element, and increment all elements by (B - max). (3)

    vector<int> Solution::findPerm(const string A, int B) {
         int n = B;
        vector<int> arr(n);

        //(1)
        arr[0]=0;
        for (int i=1; i<n; i++) {
            arr[i] = (A[i-1]=='I') ? 1 : -1;
        }

        //(2)
        int max = 0;
        for (int i=1; i<n; i++) {
            arr[i] += arr[i-1];
            max = (arr[i]>max) ? arr[i] : max;
        }

        //(3)
        for (int i=0; i<n; i++) {
            arr[i] += n-max;
        }

        return arr;
    }