C++ Solution | Divide and Conquer


#1
vector<int> Solution::findPerm(const string A, int B) {
    /* 
        Using Divide and Conquer:
            * step1: check for left neighbors
            * step2: check for right neighbors
            * Merge the two sub problems to get final result
    */
    
    // for each element decide if it should be greater than its previous element or not
    vector<int>leftCheck(B, 1);
    for(int i = 0; i < A.length(); i++) {
        if(A[i] == 'I') {
            leftCheck[i + 1] = leftCheck[i] + 1;
        }
    }
    
    // for each element decide if it should be greater than the next element or not
    vector<int>rightCheck(B, 1);
    for(int i = A.length() - 1; i >= 0; i--) {
        if(A[i] == 'D') {
            rightCheck[i] = rightCheck[i + 1] + 1;
        }
    }
    
    // to satisfy both left and right conditions
    for(int i = 0; i < B; i++) {
        leftCheck[i] = max(leftCheck[i], rightCheck[i]);
    }
    return leftCheck;

}