Minimum Number of Swaps to Make the Binary String Alternating - Video Solutions

Problem Overview: Given a binary string s, determine the minimum number of swaps required to transform it into an alternating string (either 0101... or 1010...). Any two characters can be swapped, not just adjacent ones.

Approach 1: Count Character Approach (O(n) time, O(1) space)

The key observation: an alternating string must follow one of two patterns. Either it starts with '0' (0101...) or with '1' (1010...). First count how many 0s and 1s exist. If the difference between counts is greater than 1, forming an alternating string is impossible. Otherwise, simulate both patterns by iterating through the string and counting mismatched positions. Each swap fixes two mismatches, so the answer becomes mismatch / 2. When counts are unequal, only one pattern is valid. This method works because swaps can rearrange characters anywhere, so only the mismatch count matters. The solution relies on simple counting and fits naturally with greedy reasoning.

Approach 2: Direct Index Validation (O(n) time, O(1) space)

Instead of counting mismatches indirectly, validate each index against the expected character. Build two candidate patterns: positions with even indices should contain one value while odd indices contain the other. Iterate through the string and track mismatches for each configuration. If the number of 0s equals the number of 1s, both patterns are valid and you choose the smaller swap count. If one character appears more often, that character must occupy the even indices of the final string. This approach explicitly checks index parity and performs constant-time comparisons during a single pass. It emphasizes positional constraints common in string manipulation problems.

Recommended for interviews: The Count Character Approach is typically expected. It quickly validates feasibility using character counts and calculates swaps using mismatch pairs in one pass. Interviewers like this solution because it shows clear reasoning about alternating patterns and greedy constraints. Explaining both candidate patterns and why each swap resolves two mismatches demonstrates strong problem decomposition.