10032. Remove Adjacent Almost-Equal Characters
You are given a 0-indexed string word.
In one operation, you can pick any index i of word and change word[i] to any lowercase English letter.
Return the minimum number of operations needed to remove all adjacent almost-equal characters from word.
Two characters a and b are almost-equal if a == b or a and b are adjacent in the alphabet.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
int removeAlmostEqualCharacters(string s) {
vector<int> dp(26,1);
dp[s[0] - 'a'] = 0;
for(int i = 1; i < s.length(); i++) {
vector<int> dpp(26,INT_MAX);
int x = s[i] - 'a';
for(int j = 0; j < 26; j++) {
int c = (x != j), best = INT_MAX;
for(int k = 0; k < 26; k++) {
if(abs(j-k) <= 1) continue;
best = min(best, dp[k]);
}
dpp[j] = min(dpp[j], c + best);
}
swap(dp,dpp);
}
return *min_element(begin(dp),end(dp));
}
};
|
