BOJ 16472古猫


https://www.acmicpc.net/problem/16472
1秒、512 MBメモリ
input :
  • N(1 < N ≤ 26)
  • 文字列が与えられます.(1≦文字列長≦100000)
  • output :
  • 翻訳機が認識できる最大文字列長
  • 条件:
  • beta版の翻訳機は、N種類のアルファベットの連続文字列しか認識できない文字列を与えた.
  • この問題に対して重要なのは,これまでに出現したアルファベット数,アルファベット種を記録することである.
    また,前から1文字ずつ減らすと,現在のansに存在する答えよりも長い文字列は存在しないため,アルファベットのタイプのみを考慮すればよい.
    したがって,alpha配列の長さを26に設定し,各アルファベットが何回出現したかを記録する必要がある.
    cnt変数に現在表示されているアルファベットタイプを記録させます.
    cntがnより長い場合は、n−1までwhile文startを後方に移動し続けます.
    import sys
    
    n = int(sys.stdin.readline())
    data = list(sys.stdin.readline().strip())
    alpha = [0] * 26
    start, length, ans, cnt = 0, 1, 0, 1
    alpha[ord(data[start]) - 97] += 1
    
    for end in range(1, len(data)):
        idx = ord(data[end]) - 97
    
        if alpha[idx] == 0:
            cnt += 1
        length += 1
        alpha[idx] += 1
    
        if cnt <= n:
            ans = max(ans, length)
        else:
            while start < end and cnt > n:
                idx = ord(data[start]) - 97
                alpha[idx] -= 1
                start += 1
                length -= 1
                if alpha[idx] == 0:
                    cnt -= 1
    print(ans)