Min Moves to Make String Without 3 Identical Consecutive Letters
Description:
2 min readMay 29, 2020
Solution:
To solve this task we need to find sequences of the same letters and if the sequence is longer than 3 divide length of this sequence to 3 and add result of the division to counters of needed moves.
Example of work:
3 consecutive: baaab, replace the middle a (3 / 3 == 1)
4 consecutive: baaaab, replace the third a (4 / 3 == 1)
5 consecutive: baaaaab, replace the third a (5 / 3 == 1)6 consecutive: baaaaaab -> baabaaab -> baaab -> bab with 2 replacements (6 / 3 == 2)10 consecutive: baaaaaaaaaab -> baabaaaaaaab -> baaaaaaab -> baaaab -> baab with 3 replacements (10 / 3 == 3)
Therefore, we can see the rule: counter += (consecutive char number) / 3
In C++ it will looks like:
int solution(const string & s) {
int res = 0, s_size = s.size(); for(int i = 0; i < s_size;) {
int next = i + 1; // if we meet sequence of the same letters
// scan the string to find length of this sequence
while( (next < s_size) && (s[i] == s[next]) ) { next++; } // Here "next - i" is length of the sequence
// Each third letter should be changed to remove
// too long sequences
res += (next - i) / 3;
i = next; // skip processed letters
}
return res;
}
Repository with the full project you can find here.
Return to the table of contents.
