package leetcode;

/**
 * https://leetcode.com/problems/minimum-deletions-to-make-string-balanced/
 */
public class Problem1643 {
    public int minimumDeletions(String s) {
        int countA = 0;
        for (char c : s.toCharArray()) {
            if (c == 'a') {
                countA++;
            }
        }
        int answer = countA;
        int countB = 0;
        for (char c : s.toCharArray()) {
            if (c == 'a') {
                countA--;
            } else {
                countB++;
            }
            if (countA + countB < answer) {
                answer = countA + countB;
            }
        }
        return answer;
    }
}

@@ -302,32 +302,154 @@
     %7D%0A        %7D%0A
+        // In the worst case, delete all As, so this is the initial value.%0A        // (not the optimal answer obviously).%0A
         int answ
@@ -574,38 +574,269 @@
     
-countA--;%0A            %7D else %7B
+// countA-- here means we want to keep A at this position, but delete%0A                // all other As after this position (to the right).%0A                countA--;%0A            %7D else %7B%0A                // countB++ here means B we want to delete at this position.
 %0A   
@@ -884,20 +884,19 @@
         
-if (
+// 
 countA +
@@ -907,75 +907,388 @@
 ntB 
-%3C answer) %7B%0A                answer = countA + countB;%0A            %7D
+here means As that we didn't delete + Bs we have deleted%0A            // so far.%0A            // Example:%0A            //         a b a a a b b b%0A            // countA: 3 3 2 1 0 0 0 0%0A            // countB: 0 1 1 1 1 2 3 4%0A            // ----------------------- +%0A            // answer: 3 4 3 2 1 2 3 4 --%3E get the min, i.e. 1%0A            answer = Math.min(answer, countA + countB);
 %0A   

Update problem 1643