AtCoder Grand Contest 016: A - Shrinking

solution

最終的に残る文字種を総当たり。 文字種$L = 26$が掛かって$O(L|s|^2)$。

implementation

#!/usr/bin/env python3
import string
s = input()
result = float('inf')
for last in string.ascii_lowercase:
    t = list(s)
    while not all(c == last for c in t):
        for i in range(len(t)):
            if last in t[i : i + 2]:
                t[i] = last
        t.pop()
    result = min(result, len(s) - len(t))
print(result)