Break Adjacent Duplicate Characters

Break Adjacent Duplicate Characters

Given an array of strings words consisting solely of lowercase English letters, determine the minimum number of character replacements required for each word so that no two adjacent characters are identical. In one operation, you may replace any character with any other lowercase English letter.

Return an array of integers where the i-th integer represents the minimum number of operations required for words[i].

Function Signature

def min_replacements(words: list[str]) -> list[int]:
    pass

Input

• words: A list of strings, where each string contains only lowercase English letters ('a' - 'z').

Output

• Returns a list of integers containing the minimum replacements for each corresponding string in words.

Constraints

• 1 <= len(words) <= 10^5
• 1 <= len(words[i]) <= 10^5
• The total length of all strings in words does not exceed 2 * 10^5.
• Each words[i] consists only of lowercase English letters.

Examples

Example 1

Input: words = ["ab", "aaa", "bookkeeper"]
Output: [0, 1, 3]

Explanation:

• "ab" already has no adjacent duplicates: 0 changes.
• "aaa" can be changed to "aba": 1 change.
• In "bookkeeper", adjacent pairs are 'oo', 'kk', and 'ee'. Replacing one letter in each pair (e.g., "bo1ke2pe3r") requires 3 changes.

Example 2

Input: words = ["baaaa", "c"]
Output: [2, 0]

Explanation:

• In "baaaa", the run of 'a's has length 4. Changing 2 of them (e.g., indices 2 and 4 to 'b') yields "baba", which has no adjacent duplicates: 2 changes.
• "c" has length 1: 0 changes.

Edge Cases

• Single-character strings require 0 replacements.
• Strings with all identical characters of length k require k // 2 replacements.