How to Minimize Flips to Make a Binary String Strictly Increasing (DP Solution)

Problem

Given a string s of length 0 < len(s) < 100000 consisting only of characters 'A' and 'B'. You may flip any character (A↔B). Find the minimum number of flips required to make s strictly increasing, i.e., all 'A' s appear before any 'B' s (non‑decreasing lexicographic order).

Input / Output

Input: a single line containing s.

Output: a single integer – the minimal number of flips.

Examples

Input: AABBA Output: 1 (flip the last A to B → AABBB).

Input: ABABBA Output: 2 (e.g., transform to ABBBBB or AAABBB).

Solution Overview

This problem is equivalent to LeetCode 926 “Flip String to Monotone Increasing”. A linear‑time dynamic programming (state DP) solves it.

DP definition

Let dp[i][0] be the minimal flips needed for the prefix s[0…i] when the i ‑th character is forced to be 'A'.

Let dp[i][1] be the minimal flips needed for the same prefix when the i ‑th character is forced to be 'B'.

Transition

If s[i] == 'A': dp[i][0] = dp[i-1][0] (keep 'A'). dp[i][1] = min(dp[i-1][0], dp[i-1][1]) + 1 (flip current to 'B').

If s[i] == 'B': dp[i][0] = dp[i-1][0] + 1 (flip current to 'A'). dp[i][1] = min(dp[i-1][0], dp[i-1][1]) (keep 'B').

Initialization

For the first character ( i = 0):

If s[0] == 'A', dp[0] = [0, 1].

Otherwise ( s[0] == 'B'), dp[0] = [1, 0].

Result

The answer is min(dp[n-1][0], dp[n-1][1]), where n = len(s).

Space optimisation

Only the previous row is needed, so the DP can be reduced to two variables prevA and prevB, achieving O(1) extra space.

Reference Implementation (Python)

s = input().strip()
 n = len(s)

 # dpA = cost for ending with 'A', dpB = cost for ending with 'B'
 if s[0] == 'A':
     dpA, dpB = 0, 1
 else:
     dpA, dpB = 1, 0

 for ch in s[1:]:
     if ch == 'A':
         newA = dpA                     # keep 'A'
         newB = min(dpA, dpB) + 1       # flip to 'B'
     else:  # ch == 'B'
         newA = dpA + 1                 # flip to 'A'
         newB = min(dpA, dpB)           # keep 'B'
     dpA, dpB = newA, newB

 print(min(dpA, dpB))

Complexity Analysis

Time: O(n) – a single pass over the string.

Space: O(1) – only two integer variables are stored.