Minimum Deletions to Make Alternating Substring - Solution & Explanation

Problem Overview: You are given a string and need the minimum number of deletions required so that the remaining characters form an alternating substring (no two adjacent characters are equal). Deletions can occur at any index, but the relative order of the remaining characters must stay the same.

Approach 1: Brute Force Substring Enumeration (O(n³) time, O(1) space)

Enumerate every possible substring and simulate deletions needed to make that substring alternating. For each substring s[i..j], iterate through characters and count how many adjacent duplicates must be removed to maintain an alternating pattern. This approach checks all O(n^2) substrings and scans each substring in O(n). It works for very small inputs but becomes impractical once the string grows beyond a few hundred characters.

Approach 2: Greedy Alternating Scan (O(n) time, O(1) space)

An alternating string must follow one of two patterns: starting with the first character or starting with its opposite. Traverse the string and track violations where s[i] == s[i-1]. Each violation implies one deletion is required to break the duplicate pair. The key insight is that deleting one character from every equal adjacent pair ensures the resulting sequence alternates. This linear scan works when the task only involves validating or fixing the entire string.

Approach 3: Binary Indexed Tree / Fenwick Tree (O(n log n) time, O(n) space)

For larger inputs or scenarios where substring ranges must be evaluated efficiently, a segment tree or Binary Indexed Tree helps maintain prefix statistics of characters and alternating violations. Store counts of characters or mismatch positions in the Fenwick tree. While iterating the string, query prefix ranges to determine how many deletions are required to enforce alternating order inside a candidate range. Updates and prefix queries both run in O(log n), allowing the algorithm to evaluate optimal deletion strategies without rescanning the entire substring each time.

This structure is particularly useful when the solution needs repeated range queries or dynamic updates. The Fenwick tree compresses the required state into prefix sums and enables fast difference calculations between indices.

Recommended for interviews: Start by explaining the greedy observation that adjacent duplicates force deletions. That demonstrates you understand the alternating constraint. Then move to the Fenwick tree optimization, which handles large inputs and repeated range queries efficiently. Interviewers usually look for the transition from a direct scan to a data-structure-driven solution using string processing combined with indexed trees.