【Python】スライディングウィンドウ法について(2)

初めに

こんにちは！スライディングウィンドウ法についてまとめる記事の第二弾です！
第一弾は以下をご覧ください！
https://zenn.dev/daichi09167/articles/d18d66080975e0

文字列にも応用可能(異なる文字をk個まで含む最長の部分文字列)

問題
文字列 s が与えられたとき、異なる文字を最大 k 個まで含む最長の部分文字列の長さを求めよ。

def longest_substring_with_k_distinct(s: str, k: int) -> int:
    if k == 0:
        return 0
    
    char_count = {}
    left = 0
    max_length = 0
    
    for right in range(len(s)):
        char_count[s[right]] = char_count.get(s[right], 0) + 1
        
        while len(char_count) > k:
            char_count[s[left]] -= 1
            if char_count[s[left]] == 0:
                del char_count[s[left]]
            left += 1
        
        max_length = max(max_length, right - left + 1)
    
    return max_length

# 使用例
s = "eceba"
k = 2
print(longest_substring_with_k_distinct(s, k))  # 出力: 3

ポイント

right を増やしながら文字を char_count に追加し、異なる文字の数が k を超えたら left を増やして調整する。

文字列にも応用可能(重複する文字を含まない最長の部分文字列)

問題
文字列 s が与えられたとき、重複する文字を含まない最長の部分文字列の長さを求めなさい。

def longest_unique_substring(s: str) -> int:
    # 文字列の開始位置と現在の最長部分文字列の長さを追跡
    start = 0
    max_length = 0
    char_map = {}  # 文字が出現した最後の位置を保存するマップ

    for end in range(len(s)):
        if s[end] in char_map and char_map[s[end]] >= start:
            # すでに重複している場合、開始位置を更新
            start = char_map[s[end]] + 1
        char_map[s[end]] = end  # 現在の文字の位置を更新
        max_length = max(max_length, end - start + 1)  # 最長部分文字列の長さを更新

    return max_length

# 使用例
s = "abcabcbb"
print(longest_unique_substring(s))  # 出力: 3