Loading…

easyStrings0Frequently asked

Alternating Characters

Q: How do you solve Alternating Characters using the Rebuild the Alternating String (Naive) approach?

When to use it: Mention to show you understand the mechanics, then point out it does extra work versus pure counting. The literal reading is: construct the alternating result, then report how many characters you dropped. Walk the string, track the last character you decided to keep, and append the current character only when it differs. **Why it is correct.** Keeping a character only when it differs from the previous *kept* one is exactly the greedy rule that produces a maximal alternating subsequence. Two equal neighbours can never both survive, so every survivor differs from its predecessor — the result is alternating by construction. **Why the deletion count falls out.** Every input character is either kept or dropped. If `kept` characters survive, then `|s| − kept` were deleted. Subtracting the two lengths gives the answer. **Why we don't ship it.** It is correct but wasteful: you allocate an `O(n)` buffer purely to throw it away after measuring its length. The problem only wants the *count*, and the count is fully determined by how many times two equal characters touch — which you can tally without storing anything. Use this version to explain the mechanics, then collapse it into the counting solution. Time complexity: O(n). Space complexity: O(n).

Q: How do you solve Alternating Characters using the Count Adjacent Equal Pairs (Optimal) approach?

When to use it: The intended answer. Phrase it as 'the minimum deletions equals the number of adjacent equal pairs'. Walk the string from index 1 and increment a counter every time the current character equals the one before it. That counter is the answer. **Why a collision forces exactly one deletion.** Consider a maximal *run* of identical characters — say `AAAA`. To make it valid, only one of those `A`s may remain, so you must delete `k − 1` of them for a run of length `k`. Now count the adjacent equal pairs inside that run: positions `(0,1), (1,2), (2,3)` — exactly `k − 1` of them. Run length minus one equals the number of internal collisions. So counting collisions counts forced deletions, run by run. **Why summing over the whole string is still exact.** Distinct runs are separated by a character change, and a character change is *not* a collision, so runs never share or double-count pairs. Adding up `(k − 1)` across every run is the same as adding `1` for every adjacent equal pair anywhere in the string. The grand total is the minimum number of deletions. **Why this is optimal, not just correct.** You can never do better than `k − 1` deletions in a run of `k` equal characters — fewer would leave two equal neighbours somewhere. And you never need more, because deleting down to one survivor per run already makes the string alternating. So the collision count is simultaneously a lower bound and an achievable upper bound — it *is* the optimum. **Why no extra space.** You never store the result string; you only compare each character with its predecessor and bump an integer. That's `O(1)` auxiliary space regardless of input size. Time complexity: O(n). Space complexity: O(1).

Arrays & Hashing · 29 of 83 · 6 min

You are given a string s containing only the characters A and B. A string is alternating if no two adjacent characters are the same (e.g. ABAB, BABA).

In one operation you may delete any single character. Return the minimum number of deletions required to turn s into an alternating string.

In plain English

Wherever two equal characters sit next to each other, one of them has to go. A run of identical characters of length k (say AAAA) must collapse to a single character, costing k − 1 deletions. You are not asked for the resulting string — only the count — so you can sum those forced deletions directly by counting adjacent equal pairs.

Examples

Example 1

Input: s = "AAAA"
Output: 3
Note: One run of 4 identical characters collapses to a single A: delete 3. Adjacent equal pairs: (0,1), (1,2), (2,3) = 3.

Example 2

Input: s = "BBBBB"
Output: 4
Note: Run of 5 → keep 1, delete 4. Four adjacent equal pairs.

Example 3

Input: s = "ABABABAB"
Output: 0
Note: Already alternating — no adjacent pair is equal, so nothing to delete.

Example 4

Input: s = "AABAAB"
Output: 2
Note: Collisions at index 1 (AA) and index 4 (AA). Result after deletion: ABAB.

Constraints

1 ≤ |s| ≤ 10⁵
s consists only of the characters 'A' and 'B'
Only deletions are allowed (no insertions or replacements)

Clarifying questions4First question: Does the alphabet contain only A and B?Explore questions

Q1.Does the alphabet contain only A and B?
Yes, by the prompt. But the counting solution doesn't depend on that — it works for any alphabet, since the rule is purely 'no two adjacent equal'.
Q2.Can I use insertions or replacements?
No, deletions only. If replacements were allowed the answer would still be the same here, but framing it as deletions keeps the greedy count exact.
Q3.Do I return the count or the final string?
The count of deletions. That's why we can avoid building any output and just tally collisions.
Q4.What about an empty or single-character string?
Already alternating — zero deletions. The loop starts at index 1, so length-0 or length-1 inputs return 0 naturally.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

You never need to decide which character to delete — you only need to count how many adjacent pairs are equal. Walk the string once and count every position i where s[i] == s[i-1]. That count is the minimum number of deletions, because each equal-neighbour collision forces exactly one removal. O(n) time, O(1) space.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you realise you don't have to simulate deletions at all — that the answer is a pure count of adjacent equal pairs, derivable from a single left-to-right scan.

Where candidates slip

Building a new string by skipping duplicates and then computing the difference in lengths — correct but more work and more bug surface than just counting collisions.

How to stand out

Argue why counting is optimal: in any maximal run of k identical characters you are forced to delete exactly k − 1, and the run contributes exactly k − 1 collisions. Sum over runs = total collisions.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Rebuild the Alternating String (Naive)	`O(n)`	`O(n)`	Mention to show you understand the mechanics, then point out it does extra work versus pure counting.	Read
2	Count Adjacent Equal Pairs (Optimal)Optimal	`O(n)`	`O(1)`	The intended answer. Phrase it as 'the minimum deletions equals the number of adjacent equal pairs'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewString s of A/BScan i = 1 .. n-1YesNoExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Rebuild the Alternating String (Naive)

TimeO(n)SpaceO(n)

Mention to show you understand the mechanics, then point out it does extra work versus pure counting.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Imagine literally producing the alternating string: scan left to right and keep a character only if it differs from the last one you kept.

2Hint 2Explore hint

Append each kept character to a builder. The number of deletions is then |s| minus the length of what you kept.

3Hint 3Explore hint

This is correct, but you're allocating an output buffer just to subtract two lengths — can you skip building it?

A · Core idea

The literal reading is: construct the alternating result, then report how many characters you dropped. Walk the string, track the last character you decided to keep, and append the current character only when it differs.

Why it is correct. Keeping a character only when it differs from the previous kept one is exactly the greedy rule that produces a maximal alternating subsequence. Two equal neighbours can never both survive, so every survivor differs from its predecessor — the result is alternating by construction.

Why the deletion count falls out. Every input character is either kept or dropped. If kept characters survive, then |s| − kept were deleted. Subtracting the two lengths gives the answer.

Why we don't ship it. It is correct but wasteful: you allocate an O(n) buffer purely to throw it away after measuring its length. The problem only wants the count, and the count is fully determined by how many times two equal characters touch — which you can tally without storing anything. Use this version to explain the mechanics, then collapse it into the counting solution.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "AABAAB"

i=0 'A'

nothing kept yet → keep

Statekept = "A"

Final result|s| − kept = 6 − 4 = 2

C · Code with teaching comments

Reference implementation previewpublic int alternatingCharacters(String s) { StringBuilder kept = new StringBuilder(); for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); if (kept.length() == 0 || kept.charAt(kept.length() - 1) != c) {Explore the full code

solution.javaJava

Rebuild the Alternating String (Naive) — reference

2 teaching notes

1
public int alternatingCharacters(String s) {
2
    StringBuilder kept = new StringBuilder();
3
    for (int i = 0; i < s.length(); i++) {
4
        char c = s.charAt(i);
5
        // Keep c only when the buffer is empty or its last character differs — this
6
        // enforces alternation.
7
        if (kept.length() == 0 || kept.charAt(kept.length() - 1) != c) {
8
            kept.append(c);
9
        }
10
    }
11
    // Everything not kept was deleted, so the difference is the deletion count.
12
    return s.length() - kept.length();
13
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.13 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

Building the survivors and then doing |s| − kept is the same arithmetic as counting collisions: every dropped character corresponds to exactly one collision with the character kept before it.

ComplexityO(n) time, O(n) space — One pass to build the filtered string is O(n) time, but the StringBuilder / list holding the survivors costs O(n) extra space.

E · Edge cases and pitfalls3Allocating an O(n) buffer when only a counter is needed.Explore edge cases

Pitfalls

Allocating an O(n) buffer when only a counter is needed.
Comparing against the previous INPUT character instead of the previous KEPT character — they coincide here, but the framing invites bugs.
Forgetting the empty-buffer guard before reading the last kept character.

03.2

Approach 2 of 2 · Optimal

Count Adjacent Equal Pairs (Optimal)

TimeO(n)SpaceO(1)

The intended answer. Phrase it as 'the minimum deletions equals the number of adjacent equal pairs'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

You don't need the resulting string — only its size relative to the input. What single quantity captures every forced deletion?

2Hint 2Explore hint

A character must be deleted precisely when it equals the character immediately before it. Count those positions.

3Hint 3Explore hint

Loop i from 1 to n−1; whenever s[i] == s[i−1], increment a counter. Return the counter. No extra memory.

A · Core idea

Walk the string from index 1 and increment a counter every time the current character equals the one before it. That counter is the answer.

Why a collision forces exactly one deletion. Consider a maximal run of identical characters — say AAAA. To make it valid, only one of those As may remain, so you must delete k − 1 of them for a run of length k. Now count the adjacent equal pairs inside that run: positions (0,1), (1,2), (2,3) — exactly k − 1 of them. Run length minus one equals the number of internal collisions. So counting collisions counts forced deletions, run by run.

Why summing over the whole string is still exact. Distinct runs are separated by a character change, and a character change is not a collision, so runs never share or double-count pairs. Adding up (k − 1) across every run is the same as adding 1 for every adjacent equal pair anywhere in the string. The grand total is the minimum number of deletions.

Why this is optimal, not just correct. You can never do better than k − 1 deletions in a run of k equal characters — fewer would leave two equal neighbours somewhere. And you never need more, because deleting down to one survivor per run already makes the string alternating. So the collision count is simultaneously a lower bound and an achievable upper bound — it is the optimum.

Why no extra space. You never store the result string; you only compare each character with its predecessor and bump an integer. That's O(1) auxiliary space regardless of input size.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "AABAAB"

Array state

i=1

'A' == 'A' → collision (delete 1)

i-1 ↓

[0]

i ↓

[1]

[2]

[3]

[4]

[5]

Current pointerResolved stateNot processed

Final result2

C · Code with teaching comments

solution.javaJava

Count Adjacent Equal Pairs (Optimal) — optimal

3 teaching notes

1
public int alternatingCharacters(String s) {
2
    int deletions = 0;
3
    // Start at 1 so s[i-1] is always valid; length-0/1 strings skip the loop entirely →
4
    // 0.
5
    for (int i = 1; i < s.length(); i++) {
6
        // An equal left neighbour is a forced deletion — the heart of the algorithm.
7
        if (s.charAt(i) == s.charAt(i - 1)) {
8
            // Each collision contributes exactly one removal; no decision about which
9
            // side to drop is needed.
10
            deletions++;
11
        }
12
    }
13
    return deletions;
14
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.14 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

Reframing 'minimum deletions' as 'count of local collisions' removes the entire question of which character to delete. Whenever the cost is uniform and the constraint is purely between neighbours, counting violations is the optimum — you never simulate the fix.

ComplexityO(n) time, O(1) space — A single left-to-right scan touching each character once is O(n) time. Only an integer counter is stored → O(1) extra space.

E · Edge cases and pitfalls6s = "A" — Loop never runs (no index 1) → returns 0. Single characters are already alternating.Explore edge cases

Edge cases handled

s = "A"Loop never runs (no index 1) → returns 0. Single characters are already alternating.
s = "AAAAA"Four collisions → 4 deletions, collapsing a run of 5 to a single A.
s = "ABABAB"No two neighbours equal → 0 deletions.

Pitfalls

Off-by-one: starting the loop at 0 and reading s[i-1] = s[-1] (Python wraps to the last char; Java throws).
Trying to decide which character to delete — unnecessary; the count alone is the answer.
Assuming the alphabet matters; the collision count works for any characters.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int alternatingCharacters(String s) { int deletions = 0; for (int i = 1; i < s.length(); i++) { if (s.charAt(i) == s.charAt(i - 1)) { deletions++;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Repeated-scan removal until stable

Removing one character per collision and rescanning the whole string each time is O(n²). A single pass already counts every forced deletion.

Explore the code comparison

Don't write this

count = 0
while any(s[i] == s[i+1] for i in range(len(s)-1)):
    for i in range(len(s)-1):
        if s[i] == s[i+1]:
            s = s[:i] + s[i+1:]
            count += 1
            break
return count

Write this instead

return sum(1 for i in range(1, len(s)) if s[i] == s[i-1])

Comparing to a stale 'previous' value

If you cache prev but forget to update it on a non-deletion, you compare against the wrong character and miscount.

Explore the code comparison

Don't write this

char prev = s.charAt(0);
int del = 0;
for (int i = 1; i < s.length(); i++) {
    if (s.charAt(i) == prev) del++;
    // forgot: prev = s.charAt(i);
}

Write this instead

int del = 0;
for (int i = 1; i < s.length(); i++) {
    if (s.charAt(i) == s.charAt(i - 1)) del++;
}

Off-by-one on the left neighbour

Starting at i = 0 and reading s[i-1] reads index -1; in Python that silently wraps to the last character and corrupts the count.

Explore the code comparison

Don't write this

for i in range(len(s)):
    if s[i] == s[i - 1]:
        deletions += 1

Write this instead

for i in range(1, len(s)):
    if s[i] == s[i - 1]:
        deletions += 1

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Single-pass adjacent-pair collision count

Code pattern to memorize

deletions = 0
for i in 1 .. n-1:
    if s[i] == s[i-1]:
        deletions += 1
return deletions

Rules to remember

1The answer is exactly the number of indices i where s[i] == s[i-1] — no more, no less.
2You don't choose which duplicate to delete; in a run of k equal characters you must delete k − 1, and counting collisions counts those automatically.
3Compare each character to its left neighbour, never to a fixed previous-kept variable you forgot to update.
4A single character or an already-alternating string yields 0 — the loop simply never fires.
5This is greedy and optimal in one pass; there is no need to rebuild the string.

Use this pattern when

You must make a string 'alternating' or 'no two adjacent equal' with minimum edits
Deletions only (not replacements) and the cost is uniform per deletion
The decision at each position depends only on the immediate neighbour
You can count collisions instead of simulating the removals

Choose another pattern when

Replacements or insertions are allowed too → it becomes an edit-distance / DP problem
You must output the resulting string, not just the count → still O(n) but you build output
'Alternating' means a strict A/B/A/B alphabet, not merely 'no two adjacent equal' → different rule
Costs differ per character → greedy collision count no longer equals the optimum

Interview takeaway

When deletions are uniform and the constraint is purely local ('no two adjacent equal'), the minimum number of deletions equals the number of adjacent equal pairs. Counting collisions beats simulating removals — the same idea powers 'remove adjacent duplicates' and run-length compression problems.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternLocal-constraint collision counting. When deletions are uniform and the only rule is 'no two adjacent equal', the minimum number of deletions equals the number of adjacent equal pairs — count violations in one pass instead of simulating fixes. The same run-length insight underlies adjacent-duplicate removal and string compression.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Remove All Adjacent Duplicates In String
Coming soon
Same collision idea but you must output the reduced string — use a stack.
Remove All Adjacent Duplicates in String II
Coming soon
Collapse runs of length k with a stack of (char, count) pairs.
Minimum deletions for a strict A/B alternation
Coming soon
If 'alternating' means a fixed A/B/A/B template, compare to both templates and take the cheaper.
String Compression
Coming soon
Run-length thinking again: count each maximal run instead of just collisions.

Same pattern

←

Frequency Queries

Continue · Next problem

Caesar Cipher

easyStrings0Frequently asked

Alternating Characters

Arrays & Hashing · 29 of 83 · 6 min

You are given a string s containing only the characters A and B. A string is alternating if no two adjacent characters are the same (e.g. ABAB, BABA).

In one operation you may delete any single character. Return the minimum number of deletions required to turn s into an alternating string.

In plain English

Examples

Example 1

Input: s = "AAAA"
Output: 3
Note: One run of 4 identical characters collapses to a single A: delete 3. Adjacent equal pairs: (0,1), (1,2), (2,3) = 3.

Example 2

Input: s = "BBBBB"
Output: 4
Note: Run of 5 → keep 1, delete 4. Four adjacent equal pairs.

Example 3

Input: s = "ABABABAB"
Output: 0
Note: Already alternating — no adjacent pair is equal, so nothing to delete.

Example 4

Input: s = "AABAAB"
Output: 2
Note: Collisions at index 1 (AA) and index 4 (AA). Result after deletion: ABAB.

Constraints

1 ≤ |s| ≤ 10⁵
s consists only of the characters 'A' and 'B'
Only deletions are allowed (no insertions or replacements)

Clarifying questions4First question: Does the alphabet contain only A and B?Explore questions

Q1.Does the alphabet contain only A and B?
Yes, by the prompt. But the counting solution doesn't depend on that — it works for any alphabet, since the rule is purely 'no two adjacent equal'.
Q2.Can I use insertions or replacements?
No, deletions only. If replacements were allowed the answer would still be the same here, but framing it as deletions keeps the greedy count exact.
Q3.Do I return the count or the final string?
The count of deletions. That's why we can avoid building any output and just tally collisions.
Q4.What about an empty or single-character string?
Already alternating — zero deletions. The loop starts at index 1, so length-0 or length-1 inputs return 0 naturally.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you realise you don't have to simulate deletions at all — that the answer is a pure count of adjacent equal pairs, derivable from a single left-to-right scan.

Where candidates slip

Building a new string by skipping duplicates and then computing the difference in lengths — correct but more work and more bug surface than just counting collisions.

How to stand out

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Rebuild the Alternating String (Naive)	`O(n)`	`O(n)`	Mention to show you understand the mechanics, then point out it does extra work versus pure counting.	Read
2	Count Adjacent Equal Pairs (Optimal)Optimal	`O(n)`	`O(1)`	The intended answer. Phrase it as 'the minimum deletions equals the number of adjacent equal pairs'.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Rebuild the Alternating String (Naive)

TimeO(n)SpaceO(n)

Mention to show you understand the mechanics, then point out it does extra work versus pure counting.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Imagine literally producing the alternating string: scan left to right and keep a character only if it differs from the last one you kept.

2Hint 2Explore hint

Append each kept character to a builder. The number of deletions is then |s| minus the length of what you kept.

3Hint 3Explore hint

This is correct, but you're allocating an output buffer just to subtract two lengths — can you skip building it?

A · Core idea

Why the deletion count falls out. Every input character is either kept or dropped. If kept characters survive, then |s| − kept were deleted. Subtracting the two lengths gives the answer.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "AABAAB"

i=0 'A'

nothing kept yet → keep

Statekept = "A"

Final result|s| − kept = 6 − 4 = 2

C · Code with teaching comments

solution.javaJava

Rebuild the Alternating String (Naive) — reference

2 teaching notes

1
public int alternatingCharacters(String s) {
2
    StringBuilder kept = new StringBuilder();
3
    for (int i = 0; i < s.length(); i++) {
4
        char c = s.charAt(i);
5
        // Keep c only when the buffer is empty or its last character differs — this
6
        // enforces alternation.
7
        if (kept.length() == 0 || kept.charAt(kept.length() - 1) != c) {
8
            kept.append(c);
9
        }
10
    }
11
    // Everything not kept was deleted, so the difference is the deletion count.
12
    return s.length() - kept.length();
13
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.13 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

Building the survivors and then doing |s| − kept is the same arithmetic as counting collisions: every dropped character corresponds to exactly one collision with the character kept before it.

ComplexityO(n) time, O(n) space — One pass to build the filtered string is O(n) time, but the StringBuilder / list holding the survivors costs O(n) extra space.

E · Edge cases and pitfalls3Allocating an O(n) buffer when only a counter is needed.Explore edge cases

Pitfalls

Allocating an O(n) buffer when only a counter is needed.
Comparing against the previous INPUT character instead of the previous KEPT character — they coincide here, but the framing invites bugs.
Forgetting the empty-buffer guard before reading the last kept character.

03.2

Approach 2 of 2 · Optimal

Count Adjacent Equal Pairs (Optimal)

TimeO(n)SpaceO(1)

The intended answer. Phrase it as 'the minimum deletions equals the number of adjacent equal pairs'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

You don't need the resulting string — only its size relative to the input. What single quantity captures every forced deletion?

2Hint 2Explore hint

A character must be deleted precisely when it equals the character immediately before it. Count those positions.

3Hint 3Explore hint

Loop i from 1 to n−1; whenever s[i] == s[i−1], increment a counter. Return the counter. No extra memory.

A · Core idea

Walk the string from index 1 and increment a counter every time the current character equals the one before it. That counter is the answer.

Why no extra space. You never store the result string; you only compare each character with its predecessor and bump an integer. That's O(1) auxiliary space regardless of input size.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "AABAAB"

Array state

i=1

'A' == 'A' → collision (delete 1)

i-1 ↓

[0]

i ↓

[1]

[2]

[3]

[4]

[5]

Current pointerResolved stateNot processed

Final result2

C · Code with teaching comments

solution.javaJava

Count Adjacent Equal Pairs (Optimal) — optimal

3 teaching notes

1
public int alternatingCharacters(String s) {
2
    int deletions = 0;
3
    // Start at 1 so s[i-1] is always valid; length-0/1 strings skip the loop entirely →
4
    // 0.
5
    for (int i = 1; i < s.length(); i++) {
6
        // An equal left neighbour is a forced deletion — the heart of the algorithm.
7
        if (s.charAt(i) == s.charAt(i - 1)) {
8
            // Each collision contributes exactly one removal; no decision about which
9
            // side to drop is needed.
10
            deletions++;
11
        }
12
    }
13
    return deletions;
14
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.14 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

ComplexityO(n) time, O(1) space — A single left-to-right scan touching each character once is O(n) time. Only an integer counter is stored → O(1) extra space.

E · Edge cases and pitfalls6s = "A" — Loop never runs (no index 1) → returns 0. Single characters are already alternating.Explore edge cases

Edge cases handled

s = "A"Loop never runs (no index 1) → returns 0. Single characters are already alternating.
s = "AAAAA"Four collisions → 4 deletions, collapsing a run of 5 to a single A.
s = "ABABAB"No two neighbours equal → 0 deletions.

Pitfalls

Off-by-one: starting the loop at 0 and reading s[i-1] = s[-1] (Python wraps to the last char; Java throws).
Trying to decide which character to delete — unnecessary; the count alone is the answer.
Assuming the alphabet matters; the collision count works for any characters.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int alternatingCharacters(String s) { int deletions = 0; for (int i = 1; i < s.length(); i++) { if (s.charAt(i) == s.charAt(i - 1)) { deletions++;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Repeated-scan removal until stable

Removing one character per collision and rescanning the whole string each time is O(n²). A single pass already counts every forced deletion.

Explore the code comparison

Don't write this

count = 0
while any(s[i] == s[i+1] for i in range(len(s)-1)):
    for i in range(len(s)-1):
        if s[i] == s[i+1]:
            s = s[:i] + s[i+1:]
            count += 1
            break
return count

Write this instead

return sum(1 for i in range(1, len(s)) if s[i] == s[i-1])

Comparing to a stale 'previous' value

If you cache prev but forget to update it on a non-deletion, you compare against the wrong character and miscount.

Explore the code comparison

Don't write this

char prev = s.charAt(0);
int del = 0;
for (int i = 1; i < s.length(); i++) {
    if (s.charAt(i) == prev) del++;
    // forgot: prev = s.charAt(i);
}

Write this instead

int del = 0;
for (int i = 1; i < s.length(); i++) {
    if (s.charAt(i) == s.charAt(i - 1)) del++;
}

Off-by-one on the left neighbour

Starting at i = 0 and reading s[i-1] reads index -1; in Python that silently wraps to the last character and corrupts the count.

Explore the code comparison

Don't write this

for i in range(len(s)):
    if s[i] == s[i - 1]:
        deletions += 1

Write this instead

for i in range(1, len(s)):
    if s[i] == s[i - 1]:
        deletions += 1

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Single-pass adjacent-pair collision count

Code pattern to memorize

deletions = 0
for i in 1 .. n-1:
    if s[i] == s[i-1]:
        deletions += 1
return deletions

Rules to remember

1The answer is exactly the number of indices i where s[i] == s[i-1] — no more, no less.
2You don't choose which duplicate to delete; in a run of k equal characters you must delete k − 1, and counting collisions counts those automatically.
3Compare each character to its left neighbour, never to a fixed previous-kept variable you forgot to update.
4A single character or an already-alternating string yields 0 — the loop simply never fires.
5This is greedy and optimal in one pass; there is no need to rebuild the string.

Use this pattern when

You must make a string 'alternating' or 'no two adjacent equal' with minimum edits
Deletions only (not replacements) and the cost is uniform per deletion
The decision at each position depends only on the immediate neighbour
You can count collisions instead of simulating the removals

Choose another pattern when

Replacements or insertions are allowed too → it becomes an edit-distance / DP problem
You must output the resulting string, not just the count → still O(n) but you build output
'Alternating' means a strict A/B/A/B alphabet, not merely 'no two adjacent equal' → different rule
Costs differ per character → greedy collision count no longer equals the optimum

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Remove All Adjacent Duplicates In String
Coming soon
Same collision idea but you must output the reduced string — use a stack.
Remove All Adjacent Duplicates in String II
Coming soon
Collapse runs of length k with a stack of (char, count) pairs.
Minimum deletions for a strict A/B alternation
Coming soon
If 'alternating' means a fixed A/B/A/B template, compare to both templates and take the cheaper.
String Compression
Coming soon
Run-length thinking again: count each maximal run instead of just collisions.

Same pattern

←

Frequency Queries

Continue · Next problem

Caesar Cipher