Remove Equal Neighbors
National Olympiad — Regional round (2023 season)
Submission name: norepeats.cpp
Problem summary
A string uses digits 0 through K−1. Change as few digits as possible so that consecutive digits are always different.
Input
N and K, then a string of N digits without spaces.
Output
The minimum number of replacements; output −1 if impossible.
Constraints
1 ≤ N ≤ 100000; 2 ≤ K ≤ 10.
Worked example
An independently prepared example for this explanation.
Input
3 2 111
Output
1
Solution analysis
- Let dp[d] be the minimum replacements for the processed prefix when its last digit is d. At the first position, the cost is zero for the original digit and one for every other digit.
- For a new digit d, consider every previous digit p different from d. The candidate cost is dp[p] plus one if d differs from the input digit. Only the previous row is needed.
- For 111 with K=2, changing the middle digit produces 101 at cost one. This also explains why treating equal runs independently is unsafe for K=2: the final string must be one of two alternating strings.
Why it works
Inductively dp records the optimal cost for each possible final digit. Every valid extension has a different previous digit, and every such extension is tested. The minimum final state is the unrestricted optimum.
Watch out. Compare against the original character when charging a replacement. Under K≥2 a valid alternating string always exists, so −1 is never needed.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
int main() {
int n, k;
string s;
cin >> n >> k >> s;
vector<int> dp(k);
for (int digit = 0; digit < k; digit++) {
dp[digit] = digit != s[0] - '0';
}
for (int i = 1; i < n; i++) {
// Only extensions with a different previous digit are legal.
vector<int> next(k, n + 1);
for (int digit = 0; digit < k; digit++) {
for (int previous = 0; previous < k; previous++) {
if (digit != previous) {
next[digit] = min(next[digit], dp[previous] + (digit != s[i] - '0'));
}
}
}
dp = next;
}
cout << *min_element(dp.begin(), dp.end()) << '\n';
}