3208: Alternating-Groups-II
Medium
My first thought was that a sliding window might just be the key to success!
Unfortunately, I realised that this was not optimal,
as the most important statistic to be tracking is the
current length of alternating elements,
alternating_length, which can just be tracked with
one iteration. This is because, if
alternating_length is greater than or
equal to k, we know that the current number
of alternating groups length k is
equal to alternating_length-k+1.
Knowing this and iterating through
colors.size()+k-1 elements (using modulo
to wrap back to the start), it means we can calculate the number
of alternating group in just one
pass.
Code:
class Solution {
public:
int numberOfAlternatingGroups(vector<int>& colors, int k) {
int alternating_length = 1;
int ans = 0;
for (int i = 1; i < colors.size()+k-1; ++i) {
int prev_index = (i-1)%colors.size();
int curr_index = i%colors.size();
if (colors[prev_index] != colors[curr_index]) {
++alternating_length;
} else {
if (alternating_length >= k) {
ans += alternating_length - k + 1;
}
alternating_length = 1;
}
}
if (alternating_length >= k) {
ans += alternating_length - k + 1;
}
return ans;
}
};