Given an array of size $N$. I need to find the count of values in range $[L, R]$ which are repeated at least three times in successive positions (i.e., the value occurs contiguously three times).
For eg- \begin{align*} A&= 1,1,1,2,2,1,5,1,1,2,2,2,5,5 \\ L&=0,\ R=3\,, \end{align*} the answer would be 1 (1,1,1) and 2 (2,2,2).
I tried it by doing the following:
answer = 0
count[] = 0
for i in {l..r}:
count[array[i]]++
if count[array[i]] == 3:
answer++
But this will count frequencies all over the range and not just the contiguous ones. So the answer will include $5$ as well where as it shouldn't.
How do I treat any element that starts again after some other integers come in between to be different (like here I need to treat $5$'s count differently) and consider it again for it be $\geq 3$ ? Like can I hash them somehow?
Update :Logic being same, some modification in code. I shift the $L,R$ as the function is called multiple times and increase and decrease the count.
add(position):
count[array[position]]++
if count[array[position]] == 3:
answer++
remove(position):
count[array[position]]--
if count[array[position]] == 2:
answer--
currentL = 0
currentR = 0
answer = 0
count[] = 0
for given L,R
// currentL should go to L, currentR should go to R
while currentL < L:
remove(currentL)
currentL++
while currentL > L:
add(currentL)
currentL--
while currentR <= R:
add(currentR)
currentR++
while currentR >R+1 :
remove(currentR)
currentR--
output answer
I need to calculate for many pairs of L,R .So I need an efficient algorithm. The above algorithm seems to do so.
But How do I differentiate the contiguous triplets here ?