Minimum Character Replacements So No Two Adjacent Characters Are Equal
Company: Headlands
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Online Assessment
Given a string `s` of lowercase English letters, one operation replaces the character at any single position with any lowercase English letter. Return the minimum number of operations needed so that no two adjacent characters in the resulting string are equal.
### Function Signature
```python
def min_replacements(s: str) -> int:
```
### Rules
- Each operation changes exactly one position. The replacement may be any lowercase letter, including one that already appears elsewhere in `s`.
- Only replacements are allowed; characters cannot be inserted, deleted, or reordered.
- The resulting string is valid when `s[i] != s[i + 1]` for every `0 <= i < len(s) - 1`. A string of length 1 is always valid.
- Return a single integer: the minimum number of operations. Several different resulting strings may achieve that minimum, but the count itself is unique, so only the count is returned. A string that is already valid returns `0`.
### Constraints
- `1 <= len(s) <= 100000`
- Every character of `s` is a lowercase English letter from `a` to `z`.
### Examples
Input: `s = "aab"`
Output: `1`
Replacing the character at index 1 with `c` gives `"acb"`.
Input: `s = "aaaa"`
Output: `2`
Two replacements suffice, for example giving `"abab"`.
Input: `s = "abcabc"`
Output: `0`
Overview: Given a string of lowercase letters, find the minimum number of single-position replacements needed so that no two adjacent characters are equal. It tests turning an adjacency constraint into an exact minimum count, justifying why fewer operations cannot work, and handling edge cases in an efficient solution.
Read the full Headlands Data Scientist interview experience this question came from
You are given a string `s` of lowercase English letters. In one operation you may replace the character at any single position with any lowercase English letter (the replacement may be a letter that already appears elsewhere in `s`). Characters cannot be inserted, deleted, or reordered.
Return the minimum number of operations needed so that the resulting string has no two adjacent equal characters, i.e. `s[i] != s[i + 1]` for every `0 <= i < len(s) - 1`. A string of length 1 is always valid, and a string that is already valid returns `0`.
Several different resulting strings may achieve the minimum, but the count itself is unique, so only the count is returned (a single integer).
Example 1:
Input: s = "aab"
Output: 1
Explanation: Replacing the character at index 1 with 'c' gives "acb".
Example 2:
Input: s = "aaaa"
Output: 2
Explanation: Two replacements suffice, for example giving "abab".
Example 3:
Input: s = "abcabc"
Output: 0
Constraints:
- 1 <= len(s) <= 100000
- Every character of s is a lowercase English letter from 'a' to 'z'.
The answer is at most len(s) / 2 = 50000, so it always fits in a 32-bit signed integer.
Constraints
- 1 <= len(s) <= 100000
- Every character of s is a lowercase English letter from 'a' to 'z'.
Examples
Input: ('a',)
Expected Output: 0
Explanation: A single character is always valid.
Input: ('zz',)
Expected Output: 1
Explanation: Two equal letters at the alphabet edge need one change.
Hints
- Think about which parts of the string actually need to change: look at stretches of consecutive identical characters.
- Can a change inside one stretch of identical characters ever affect a different stretch?
- For a single stretch of identical characters of length L, find a lower bound on the changes needed and check whether it can be achieved.