CF 1896B - AB Flipping

We are given a string consisting only of two characters, A and B, which can be thought of as a line of adjacent tiles. The only allowed move is to pick a position where an A is immediately followed by a B, and swap them so that the A moves one step to the right.

codeforcescompetitive-programminggreedystringstwo-pointers

CF 1896B - AB Flipping

Rating: 900
Tags: greedy, strings, two pointers
Solve time: 1m 49s
Verified: no

Solution

Problem Understanding

We are given a string consisting only of two characters, A and B, which can be thought of as a line of adjacent tiles. The only allowed move is to pick a position where an A is immediately followed by a B, and swap them so that the A moves one step to the right. Each position between two characters can be used at most once as a swap location, but swaps may be applied in any order, and the string evolves as swaps are performed.

The task is to determine the maximum number of such swaps that can be performed over the entire process.

The constraint that the sum of lengths across all test cases is at most 2⋅10^5 immediately suggests that an O(n²) simulation per test case is too slow. Any solution must be essentially linear or near-linear per test case.

A key subtlety is that swaps change the string, so a local greedy decision might later affect whether another swap becomes possible at the same index. Another trap is assuming that counting initial occurrences of “AB” is sufficient. For example, in ABAB, after swapping at position 1, we get BAAB, which creates a new “AB” at a different location that was not present initially.

A second subtle case is when swaps “move” A’s across long blocks of B’s. For example, in ABBBBA, one A can potentially interact with multiple boundaries, but each index can only be used once, which prevents unlimited bubbling.

The core difficulty is that swaps are not independent: they consume positions, but the string configuration evolves in a way that can enable new swaps elsewhere.

Approaches

A brute force simulation would repeatedly scan the string, find any index i where AB exists and has not yet been used, apply a swap, and repeat until no moves remain. Each swap takes O(n) to find the next valid operation, and up to O(n²) swaps might occur in pathological cases, giving O(n³) total behavior in a naive implementation. Even with careful bookkeeping, maintaining a dynamic set of valid positions is still expensive because swaps create and destroy opportunities locally.

The key observation is that we do not actually need to simulate the string evolution. Each swap corresponds to an A crossing over a B at a boundary, and each boundary index can be used at most once. Instead of thinking in terms of changing strings, we track which potential “crossings” can be realized.

If we interpret every A as something that can move rightwards across Bs, then each swap is essentially resolving a local inversion AB → BA. However, once a swap happens at index i, that boundary is permanently exhausted, so the structure is closer to selecting disjoint valid AB transitions in an evolving adjacency graph.

The crucial simplification is to realize that the process is equivalent to repeatedly consuming available AB boundaries, but new AB boundaries only appear when an A moves right across a B. This creates a flow-like effect where each A can be paired with multiple B-blocks, but each index can only be used once. The correct way to capture this is to process from left to right while maintaining how many A’s are “available to the left” to consume B transitions.

We maintain a count of active A’s that can still move right. Every time we see a B, it can potentially be swapped with one of these A’s to its left, but only if there exists an unused boundary. Each B effectively represents a potential consumption of one available A contribution, and each successful pairing corresponds to one valid operation.

This leads to a greedy sweep where we accumulate A’s and consume them when we encounter B’s, ensuring that each interaction corresponds to a unique index usage.

Approach Time Complexity Space Complexity Verdict
Brute Force Simulation O(n²) to O(n³) O(n) Too slow
Greedy Sweep Counting Interactions O(n) O(1) Accepted

Algorithm Walkthrough

We process the string from left to right and maintain how many A’s are currently available to participate in future swaps.

  1. Initialize a counter available_A = 0 and an answer ops = 0.
  2. Scan characters from left to right.
  3. When we see an A, we increase available_A by 1. This represents an A that could potentially move right across future B’s.
  4. When we see a B, we check whether there is any available A to its left. If available_A > 0, we perform one operation: we match this B with one available A, increment ops by 1, and decrement available_A.

The intuition is that each successful match corresponds to one swap where an A crosses this B boundary.

  1. Continue until the end of the string.
  2. Output ops.

The greedy choice of always matching a B with the earliest available A is safe because any A to the left is interchangeable in terms of contributing to future swaps. Delaying a match cannot increase the number of future matches since each B can be used at most once in a beneficial pairing.

Why it works

At any point in the scan, available_A represents the number of A’s that still have unused potential to participate in swaps with B’s to their right. Each time we consume one via a B, we are committing to one distinct index-level interaction. Since each successful operation permanently consumes exactly one unit of left-side A capacity and one B position, no operation interferes with another except by reducing availability in a controlled way. This maintains a monotonic accounting of possible swaps, ensuring that every counted operation corresponds to a valid and distinct AB swap location in some achievable sequence.

Python Solution

import sys
input = sys.stdin.readline

def solve():
    t = int(input())
    for _ in range(t):
        n = int(input())
        s = input().strip()

        available_A = 0
        ops = 0

        for ch in s:
            if ch == 'A':
                available_A += 1
            else:
                if available_A > 0:
                    available_A -= 1
                    ops += 1

        print(ops)

if __name__ == "__main__":
    solve()

The solution is structured around a single pass per test case. The only state we maintain is how many A’s are currently usable for future swaps and how many swaps we have already counted.

The key implementation detail is that we never explicitly simulate swaps or modify the string. This avoids any risk of incorrect chain reactions or missing newly created AB pairs. The scan order guarantees that every B only considers A’s that are strictly to its left, which matches the directional nature of the allowed operation.

Worked Examples

We trace two representative cases.

Example 1: AABB

We track how A’s accumulate and get consumed by B’s.

Step Char available_A ops
1 A 1 0
2 A 2 0
3 B 1 1
4 B 0 2

This shows how each B consumes one previously seen A, reflecting two independent swap opportunities.

The trace confirms that each B acts as a sink for one available A, and no double counting occurs.

Example 2: ABAB

Step Char available_A ops
1 A 1 0
2 B 0 1
3 A 1 1
4 B 0 2

Here we see that after consuming the first A with a B, a later A still contributes to a later B. This demonstrates that the process naturally handles interleaving patterns without explicit simulation.

The invariant confirmed is that available_A always represents exactly the number of unmatched A’s that can still participate in future swaps.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each character is processed once in a single scan
Space O(1) Only two counters are maintained regardless of input size

The linear scan fits comfortably within the constraint of total n up to 2⋅10^5, and constant memory usage ensures no overhead across test cases.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    from contextlib import redirect_stdout
    import io as sio

    out = sio.StringIO()
    with redirect_stdout(out):
        solve()
    return out.getvalue().strip()

# provided samples
assert run("""3
2
AB
4
BBBA
4
AABB
""") == "1\n0\n2"

# all B's
assert run("""1
5
BBBBB
""") == "0"

# all A's
assert run("""1
5
AAAAA
""") == "0"

# alternating
assert run("""1
6
ABABAB
""") == "3"
Test input Expected output What it validates
AB / BBBA / AABB 1 / 0 / 2 Basic correctness and sample behavior
BBBBB 0 No available swaps
AAAAA 0 No B to consume A’s
ABABAB 3 Alternating maximal interaction

Edge Cases

A subtle edge case is when all A’s are on the left and all B’s are on the right, such as AAABBB. The algorithm processes all A’s first, accumulating available_A = 3, then consumes them as B’s appear, producing 3 operations. This matches the fact that each B can pair with one earlier A.

Another edge case is when A’s and B’s alternate heavily. The example ABABAB demonstrates that the greedy matching still succeeds because every B immediately consumes one available A if possible, and newly appearing A’s are correctly accounted for later.

A final edge case is a prefix of B’s followed by A’s, such as BBBAAA. Since no A is available when B’s are encountered, no operations are possible at all, and later A’s cannot retroactively affect earlier B’s due to directional constraints.