Polycarp Writes a String from Memory (Codeforces 1702B)
Tags: Greedy, greedy

Polycarp has a poor memory. Each day he can remember no more than $$$3$$$ of different letters. Polycarp wants to write a non-empty string of $$$s$$$ consisting of lowercase Latin letters, taking minimum number of days. In how many days will he be able to do it?Polycarp initially has an empty string and can only add characters to the end of that string.For example, if Polycarp wants to write the string lollipops, he will do it in $$$2$$$ days:   on the first day Polycarp will memorize the letters l, o, i and write lolli;  On the second day Polycarp will remember the letters p, o, s, add pops to the resulting line and get the line lollipops. If Polycarp wants to write the string stringology, he will do it in $$$4$$$ days:   in the first day will be written part str;  on day two will be written part ing;  on the third day, part of olog will be written;  on the fourth day, part of y will be written. For a given string $$$s$$$, print the minimum number of days it will take Polycarp to write it.

Input: The first line of input data contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.Each test case consists of a non-empty string $$$s$$$ consisting of lowercase Latin letters (the length of the string $$$s$$$ does not exceed $$$2 \cdot 10^5$$$) — the string Polycarp wants to construct.It is guaranteed that the sum of string lengths $$$s$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case, print a single number — minimum number of days it will take Polycarp to write the string $$$s$$$ from memory.


Sample Inputs:
6
lollipops
stringology
abracadabra
codeforces
test
f

Sample Outputs:
2
4
3
4
1
1

Solution (Python):
def BoogeyMan() -> None:
    """"""
    for _ in range(ii()):
        s = si()
        store = []
        counter = 0
        mc = 0
        idx = 0
        for i in s:
            if counter == 3:
                if i in store:
                    idx += 1
                    continue
                counter = 1
                mc += 1
                store.clear()
                store.append(i)
            elif i not in store:
                store.append(i)
                counter += 1
            idx += 1
        if counter <= 3 and idx == len(s):
            mc += 1
        if mc == 0:
            mc += 1
        p(mc)
if __name__ == '__main__':
    import os, sys, math, itertools, bisect
    from collections import deque, defaultdict, OrderedDict, Counter
    (ii, si) = (lambda : int(input()), lambda : input())
    (mi, msi) = (lambda : map(int, input().strip().split(' ')), lambda : map(str, input().strip().split(' ')))
    (li, lsi) = (lambda : list(mi()), lambda : list(msi()))
    (out, export, p, pp) = ([], lambda : print('\n'.join(map(str, out))), lambda x: out.append(x), lambda array: p(' '.join(map(str, array))))
    try:
        from baba_yaga import L, cmdIO, _generator_

        class _BoogeyMan_:

            def __init__(self) -> None:
                self.launchers = [cmdIO(), BoogeyMan(), export(), _generator_()]

            def init(self) -> None:
                for _ in self.launchers:
                    yield _
                    assert not _, 'EOF'

            def container(fun):

                def wrapper():
                    print(f'Success', end='\n')
                    fun()
                return wrapper

        @_BoogeyMan_.container
        def assembler():
            _BoogeyMan_().init()
        assembler()
    except (FileNotFoundError, ModuleNotFoundError):
        BoogeyMan()
        export()

Solution (Python):
class Solution:

    def __init__(self):
        pass

    def solve(self):
        t = int(input())
        result = []
        for i in range(t):
            s = input()
            day = 0
            count = 0
            learn = []
            for char in s:
                if count == 3 and char not in learn:
                    learn = []
                    day += 1
                    count = 0
                if char not in learn:
                    learn.append(char)
                    count += 1
            if count > 0:
                day += 1
            result.append(day)
        for x in result:
            print(x)
if __name__ == '__main__':
    sol = Solution()
    sol.solve()

Solution (Python):
import sys
put = sys.stdin.readline
t = int(put())
while t:
    t -= 1
    s = put().strip()
    memory = set()
    answer = 1
    for i in s:
        if i in memory:
            continue
        if len(memory) == 3:
            answer += 1
            memory = {i}
        else:
            memory.add(i)
    print(answer)