CF 2225B - Alternating String

We are given a binary string made of only a and b. The goal is to check whether we can turn it into a perfectly alternating string, meaning every adjacent pair of characters differs. We are allowed to perform at most one operation.

codeforcescompetitive-programmingbrute-forcegreedy

CF 2225B - Alternating String

Rating: -
Tags: brute force, greedy
Solve time: 3m 12s
Verified: no

Solution

Problem Understanding

We are given a binary string made of only a and b. The goal is to check whether we can turn it into a perfectly alternating string, meaning every adjacent pair of characters differs.

We are allowed to perform at most one operation. In that operation we pick a contiguous substring. Inside that substring we may optionally swap a with b everywhere, and then we must reverse the substring. Everything outside the chosen segment stays untouched.

So the only freedom is that we can take one interval, optionally complement it, and then reverse it.

The question is whether there exists some choice of a segment and optional complement that makes the whole string alternating.

The constraints are tight: total length over all test cases is up to 2×10^5, so any quadratic exploration over substrings is impossible. Even checking all O(n^2) segments per test case would be too slow. This pushes us toward a linear or near-linear characterization of when a single segment operation can fix the string.

A subtle edge case is when the string is already alternating. In that case, the answer must be YES without using any operation. Another case that often misleads naive approaches is when the string is “almost alternating” but has two disjoint bad regions, for example aabbaabb. Locally it looks fixable, but a single segment operation cannot independently fix two separated defect regions without disturbing the structure in between.

Approaches

A brute-force idea is to try every possible substring, simulate the operation, and check whether the resulting string is alternating. For each substring, we would potentially reverse it and optionally flip it, then validate the whole string in linear time. Since there are O(n^2) substrings and each check costs O(n), this leads to O(n^3), which is completely infeasible for n up to 2×10^5.

Even if we optimize checking by only verifying adjacency locally, we still have O(n^2) candidates, which is too large.

The key observation is that the target structure is extremely rigid. An alternating string is determined completely by its first character. Once we fix whether it starts with a or b, every position is forced. This reduces the problem to checking whether we can transform the given string into one of two fixed patterns.

Once we fix a target alternating pattern, the problem becomes a comparison between the original string and that target. The operation only rearranges one contiguous block (with possible complementation), so the effect on mismatch positions has a strong structural restriction: mismatches cannot be scattered arbitrarily if they are to be repaired by a single segment transformation.

This reduces the problem to checking whether the set of mismatch positions forms a single contiguous block for at least one of the two alternating targets.

Approach Time Complexity Space Complexity Verdict
Brute Force (all substrings simulation) O(n^3) O(n) Too slow
Optimal (mismatch interval check) O(n) O(1) Accepted

Algorithm Walkthrough

We reduce the problem to checking compatibility with two fixed alternating patterns.

  1. Construct two hypothetical target strings implicitly. One starts with a and alternates, the other starts with b and alternates. This captures all possible alternating strings.
  2. For each target, compute where the input string differs from it. Mark a position as bad if s[i] does not match the target character.
  3. If there are no bad positions, the string is already alternating and we can immediately return YES.
  4. Otherwise, check whether all bad positions lie inside a single contiguous segment. This means there exists indices l and r such that every mismatch position is between them and every position outside has no mismatch.
  5. If this holds for at least one of the two targets, return YES; otherwise return NO.

The reason this is sufficient is that the allowed operation affects exactly one contiguous block of positions. Outside that block nothing can change, so every position outside must already match the target. Inside the block, the operation can rearrange and optionally flip characters, but it cannot repair two separated mismatch regions independently.

Why it works

Fix a target alternating string t. Define an indicator d[i] = 1 if s[i] != t[i], otherwise 0. Any valid operation selects a segment [l, r] such that outside the segment the string remains unchanged, so all positions with d[i] = 1 must lie inside [l, r].

Inside the segment, the operation reverses and optionally flips characters. This transformation can only consistently correct the segment if all mismatched positions behave uniformly with respect to t, which forces all mismatches inside the segment to be aligned and not split into multiple disconnected regions. If mismatches form a single interval, the segment boundaries can be chosen exactly as that interval, making correction possible.

Thus feasibility reduces to whether the mismatch set forms one contiguous interval under at least one alternating target.

Python Solution

import sys
input = sys.stdin.readline

def ok(s, start_char):
    n = len(s)
    mismatches = 0
    first = -1
    last = -1

    for i, ch in enumerate(s):
        expected = start_char if i % 2 == 0 else ('b' if start_char == 'a' else 'a')
        if ch != expected:
            mismatches += 1
            if first == -1:
                first = i
            last = i

    if mismatches == 0:
        return True

    # check that all positions between first and last are mismatches
    for i in range(first, last + 1):
        expected = start_char if i % 2 == 0 else ('b' if start_char == 'a' else 'a')
        if s[i] == expected:
            return False

    return True

def solve():
    s = input().strip()
    if ok(s, 'a') or ok(s, 'b'):
        print("YES")
    else:
        print("NO")

if __name__ == "__main__":
    t = int(input())
    for _ in range(t):
        solve()

The core of the implementation is the ok function, which evaluates whether a fixed alternating pattern can be reached. The first loop identifies the leftmost and rightmost mismatch positions while counting how many mismatches exist. If there are none, the string already matches the target.

The second check ensures that mismatches are not split into multiple groups. If there exists a correct position inside the span between the first and last mismatch, the mismatch set is not a single interval, which immediately invalidates the possibility of fixing the string with one segment operation.

We test both possible alternating patterns because the final string could start with either character.

Worked Examples

Consider the string abbaab.

We first test the pattern starting with a, which is ababab.

i s[i] expected mismatch first last
0 a a 0 - -
1 b b 0 - -
2 b a 1 2 2
3 a b 1 2 3
4 a a 0 2 3
5 b b 0 2 3

Here mismatches occur at indices 2 and 3, and every position between them is also mismatched, so it forms one contiguous block. This passes for the first target, so the answer is YES.

Now consider ababba.

We test the same target ababab.

i s[i] expected mismatch first last
0 a a 0 - -
1 b b 0 - -
2 a a 0 - -
3 b b 0 - -
4 b a 1 4 4
5 a b 1 4 5

The mismatches are at 4 and 5, but checking the segment between first and last reveals no internal correct positions, so this is still a single interval and would pass. If instead mismatches were split, such as at positions 1 and 4 only, the middle region would contain correct matches and the check would fail, correctly rejecting it.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each test scans the string a constant number of times for the two possible targets
Space O(1) Only counters and indices are stored

The total length across all test cases is bounded by 2×10^5, so a linear scan per test case fits comfortably within time limits.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    out = io.StringIO()
    sys.stdout = out

    def ok(s, start_char):
        n = len(s)
        mismatches = 0
        first = -1
        last = -1

        for i, ch in enumerate(s):
            expected = start_char if i % 2 == 0 else ('b' if start_char == 'a' else 'a')
            if ch != expected:
                mismatches += 1
                if first == -1:
                    first = i
                last = i

        if mismatches == 0:
            return True

        for i in range(first, last + 1):
            expected = start_char if i % 2 == 0 else ('b' if start_char == 'a' else 'a')
            if s[i] == expected:
                return False

        return True

    def solve():
        s = input().strip()
        print("YES" if ok(s, 'a') or ok(s, 'b') else "NO")

    t = int(input())
    for _ in range(t):
        solve()

    return out.getvalue().strip()

# provided sample
assert run("1\nabba\n") == "YES"

# already alternating
assert run("1\nabab\n") == "YES"

# single mismatch block
assert run("1\naabb\n") == "YES"

# two separated mismatch regions
assert run("1\nabaaba\n") == "NO"

# minimum size
assert run("2\na\nb\n") == "YES\nYES"
Test input Expected output What it validates
aabb YES single contiguous correction block
abab YES already alternating
abaaba NO split mismatch regions cannot be fixed
single chars YES trivial acceptance

Edge Cases

A string that is already alternating is accepted immediately because the mismatch set is empty for both targets, so the algorithm returns YES without needing to identify any segment.

A string like aabb has mismatches only in the middle when compared to one alternating pattern, forming a single contiguous block. The algorithm correctly identifies a valid interval even though a naive view might think multiple edits are needed.

A string like ababbaab fails because mismatches appear in two separated regions. Even though each region individually could be fixed by a segment operation, a single allowed operation cannot cover both without affecting correct characters in between, which is exactly what the contiguous-block check detects.