Binary String Errors - Count Positions Violating Alternating Pattern
Question Details
Problem
A "valid" binary string strictly alternates between '0' and '1'. There are exactly two valid patterns for length n: starting with '0' or starting with '1'.
Given a binary string s,
return the minimum number of character changes needed to make it a valid alternating string.
python
def min_errors(s: str) -> int:
Example
s = "0100110"
# Pattern 0101010: mismatches at positions 2,4,5 -> 3 changes
# Pattern 1010101: mismatches at positions 0,3,6 -> 3 changes
Output: 3
s = "010"
**Output**: 0 (already valid)
Follow-ups
- Extend the definition: errors come in two types -- a
'0'where'1'expected costs 2, reverse costs 1. Minimize total cost. - What if the string can be rotated (cyclically shifted) before fixing -- how do you find the best rotation?
- Implement a function that, given the corrected string,
returns the list of indices that were changed.
4. Generalize to a string over alphabet {0,1,2} that should cycle 0,1,2,0,1,2,....
Full Details
Problem
A "valid" binary string strictly alternates between '0' and '1'. There are exactly two valid patterns for length n: starting with '0' or starting with '1'.
Given a binary string s,
return the minimum number of character changes needed to make it a valid alternating string.
python
def min_errors(s: str) -> int:
Example
s = "0100110"
# Pattern 0101010: mismatches at positions 2,4,5 -> 3 changes
# Pattern 1010101: mismatches at positions 0,3,6 -> 3 changes
Output: 3
s = "010"
**Output**: 0 (already valid)
Follow-ups
- Extend the definition: errors come in two types -- a
'0'where'1'expected costs 2, reverse costs 1. Minimize total cost. - What if the string can be rotated (cyclically shifted) before fixing -- how do you find the best rotation?
- Implement a function that, given the corrected string,
returns the list of indices that were changed.
4. Generalize to a string over alphabet {0,1,2} that should cycle 0,1,2,0,1,2,....