AtCoder Beginner Contest 210 C - Colorful Candies【Python】

https://atcoder.jp/contests/abc210/tasks/abc210_c
AtCoder ProblemsのRecommendationで Difficulty: 359、Solve Probability: 47%でした。
間に合うと思って単純に実装したところTLEとなり、解説を見て実装するもWAとなってしまったため他の方の提出コードを見ました。単純な実装では計算量がO(K(N−K+1))でO(NK)になるとのことですが、計算量の求め方がよくわかってないですね。
実際に計算してみたところ、Nが制約の最大でKがその半分の値の場合は2 * 10 **10程度になり実行時間制限を超えるようだというのはわかりました。
尺取り法を使う他の問題も解いていきたいところです。

https://qiita.com/u2dayo/items/0ae64fdedf3535aefe83 https://atcoder.jp/contests/abc210/submissions/27478365 https://atcoder.jp/contests/abc210/submissions/27598182

from collections import defaultdict
N, K = map(int, input().split())
C = list(map(int, input().split()))

d = defaultdict(int)

ans = 0
now = 0
for i in range(N):
    new_val = C[i]
    d[new_val] += 1
    if d[new_val] == 1:
        now += 1
    if i >= K:
        old_val = C[i - K]
        d[old_val] -= 1
        if d[old_val] == 0:
            now -= 1
    ans = max(ans, now)
print(ans)