Minimum Number of Changes to Make Binary String Beautiful - Video Solutions

Problem Overview: You are given a binary string s of even length. A string is considered beautiful if every consecutive pair of characters (s[0], s[1], s[2], s[3], …) contains identical values. The task is to compute the minimum number of character changes required to satisfy this rule.

Approach 1: Check Pairs of Adjacent Characters (O(n) time, O(1) space)

The simplest observation: each pair of positions must contain the same bit. Iterate through the string in steps of two and compare s[i] with s[i+1]. If the two characters differ (01 or 10), one change is required to make them equal. Either character can be flipped, so the minimum cost per mismatched pair is exactly one operation. This approach works because each pair is independent of the others—changing one pair never affects another pair. The algorithm performs a single linear scan and counts mismatches, making it optimal with O(n) time and constant O(1) space.

Approach 2: Using Sliding Window for Efficient Changes (O(n) time, O(1) space)

This approach frames the same idea using a window of size two. Maintain a sliding window over the string and process characters in pairs. For every window [i, i+1], check whether both characters match. If they differ, increment the change counter because one modification is required to make the pair uniform. After evaluating the window, move it forward by two positions to process the next pair. The sliding window interpretation is useful when you are used to solving sliding window problems or when adapting the logic to variations where window size might change. Despite the different framing, the algorithm still performs a single pass over the string.

The key insight is that the beautiful condition operates strictly on fixed-size pairs. No global restructuring or dynamic programming is required. Each pair contributes either 0 changes (if both bits match) or 1 change (if they differ). Because of this independence, a greedy local check produces the optimal result.

This problem mainly tests comfort with basic iteration and pattern recognition in string processing. Many candidates initially overthink it with frequency counts or substring replacements, but the structure of the constraint immediately reduces it to pair comparisons.

Recommended for interviews: Approach 1 is what interviewers typically expect. It shows you recognized the pair independence and implemented the greedy check in a single pass. The sliding window framing is conceptually equivalent but can help demonstrate familiarity with common algorithmic patterns.