問題
034 - There are few types of elements（★4）
ポイント
・〇〇を満たす区間 (連続する部分列) のうち、最小or最大の長さを求めよ
・〇〇を満たす区間 (連続する部分列) を数え上げよ
このような問題にはしゃくとり法が有効です。
※しゃくとり法については下記記事が参考になります。
【累積和、しゃくとり法】初級者でも解るアルゴリズム図解
実装したコードはこちらです。
コード
def main():
import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline
N, K = map(int, input().split())
A = list(map(int, input().split()))
cnt = dict() # 各種類の要素の数
kind = 0 # 種類の数
ans = 1
right = 0 # しゃくとり法の確認区間の右端インデックス
# しゃくとり法
for left in range(N): # 確認区間の左端を1つずつ右にずらす
while right < N and kind <= K: # 右端がリスト内にありかつK種類以下
if A[right] in cnt: # 右端の種類を確認する
cnt[A[right]] += 1
else:
cnt[A[right]] = 1
kind += 1
right += 1 # 確認区間の右端を1つ移動
if kind <= K: # right>=Nで抜けた場合（区間の右端が数列の最後までたどり着いた場合）
ans = max(ans, right-left)
break
else:
ans = max(ans, right - left - 1) # kind>Kなので、右端は部分列に含めない
cnt[A[left]] -= 1 # 確認区間の左端の種類の要素数を1減らす
if cnt[A[left]] == 0: # 左端の種類の要素数が0なら種類の数を1つ減らす
kind -= 1
del cnt[A[left]]
print(ans)
if __name__ == '__main__':
main()
