Minimum Letters to Delete to Get A’s before B’s with Dynamic Programming Algorithm

Given a string s consisting only of A and B, return the minimum number of letters that need to be deleted from s to get all occurrences of As before all occurrences of Bs.

Constraints
n ≤ 100,000 where n is the length of s
Example 1
Input
s = “AABBAB”
Output
1
Explanation
We can remove the last A to get AABBB.

Suppose for an index, we know the count of As in left part and count of Bs in right part.
How can we find the characters to be deleted?

Dynamic Programming to Calculate Minimum Letters to Delete

For each index/pos, we can compute how many A’s on the left and how many B’s on the right. Then we can compute the letters to delete at this point. We can pre-calculate this using O(N) loop and store it in two O(N) arrays aka Dynamic Programming Algorithm. We go through the array twice to calculate the prefix and suffix respectively aka the number of As on the left and the number of Bs on the right.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

int minimumLettersToDelete(string s) {
    int n = static_cast<int>(s.size());
    if (n == 0) return 0;
    vector<int> leftA(n, 0);
    vector<int> rightB(n, 0);
    leftA[0] = s[0] == 'A' ? 1 : 0;
    for (int i = 1; i < n; ++ i) {
        leftA[i] = leftA[i - 1] + (s[i] == 'A' ? 1 : 0);
    }
    rightB.back() = s.back() == 'B' ? 1 : 0;
    for (int i = n - 2; i >= 0; -- i) {
        rightB[i] = rightB[i + 1] + (s[i] == 'B' ? 1 : 0);
    }
    int ans = INT_MAX;
    for (int i = 0; i < n; ++ i) {
        ans = min(ans, i - leftA[i] + n - i - rightB[i]);
    }
    return ans;
}

int minimumLettersToDelete(string s) {
    int n = static_cast<int>(s.size());
    if (n == 0) return 0;
    vector<int> leftA(n, 0);
    vector<int> rightB(n, 0);
    leftA[0] = s[0] == 'A' ? 1 : 0;
    for (int i = 1; i < n; ++ i) {
        leftA[i] = leftA[i - 1] + (s[i] == 'A' ? 1 : 0);
    }
    rightB.back() = s.back() == 'B' ? 1 : 0;
    for (int i = n - 2; i >= 0; -- i) {
        rightB[i] = rightB[i + 1] + (s[i] == 'B' ? 1 : 0);
    }
    int ans = INT_MAX;
    for (int i = 0; i < n; ++ i) {
        ans = min(ans, i - leftA[i] + n - i - rightB[i]);
    }
    return ans;
}

The overall time complexty for above Dynamic Programming to calculate the minimum letters to delete in order to make all A’s come before B’s is O(N). and space complexity is O(N) where N is the number of the letters in the given string.

–EOF (The Ultimate Computing & Technology Blog) —