Discussion on "Alternating Characters Cleanup - minimum number of deletions required"

To See All Articles About Technology: Index of Lessons in Technology

Just the problem

Problem: Alternating Characters Cleanup

Description

You are given a string s consisting only of the characters 'A' and 'B'. You want to make the string "good" by deleting the minimum number of characters such that no two adjacent characters are the same.

A "good" string is one where no two adjacent characters are equal.

Your task is to find the minimum number of deletions required.

Input Format

A single line containing the string s (1 ≤ len(s) ≤ 1000), consisting only of A and B.

Output Format

An integer denoting the minimum number of deletions required.

Sample Input 1

AABAAB

Sample Output 1

2

Sample Input 2

ABABAB

Sample Output 2

0

Explanation

In the first example, one possible "good" string is ABAB, which takes 2 deletions.

In the second example, the string already alternates correctly, so no deletions are needed.


Possible Solution

s = "afafasgggewrtdg"
min_deletions = 0
last_seen_character = None

for c in s:
    if c == last_seen_character:
        min_deletions += 1
    last_seen_character = c

print(min_deletions)

Complexity

Time: O(n) — one pass through the string

Space: O(1) — only a couple of counters