longest_substring_count.py

"""With At Most Two Distinct Characters"""

from collections import Counter
def longest_substring_count_at_most_two(s):
    counter = Counter()
    fast, max_length = 0, 0
    for lag, char in enumerate(s):
        counter[char] += 1
        while len(counter) > 2:
            counter[s[fast]] -= 1
            if counter[s[fast]] == 0:
                del counter[s[fast]]
            fast += 1
        max_length = max(max_length, lag-fast+1)
    return max_length
    

cases = [
longest_substring_count_at_most_two("abcbbbbcccbdddadacb"),
longest_substring_count_at_most_two("abcbbb"),
longest_substring_count_at_most_two("cccbdddadacb"),
longest_substring_count_at_most_two("ddadab"),
longest_substring_count_at_most_two("ab"),
longest_substring_count_at_most_two("a"),
]

print("With At Most Two Distinct Characters")
for case in cases:
    print(case)

"""With At Most K Distinct Characters"""

from collections import Counter


def longest_substring_count_at_most_k(s, k):
    if len(set(s)) < k: return 0
    counter = Counter()
    left, max_length = 0, 0
    for right, char in enumerate(s):
        counter[char] += 1
        while len(counter) > k:
            counter[s[left]] -= 1
            if counter[s[left]] == 0:
                del counter[s[left]]
            left += 1
        max_length = max(max_length, right-left+1)
    return max_length
    

cases = [
longest_substring_count_at_most_k("abcbbbbcccbdddadacb", 2),
longest_substring_count_at_most_k("abcbbb", 3),
longest_substring_count_at_most_k("cccbdddadacb", 6),
longest_substring_count_at_most_k("ddadab", 2),
longest_substring_count_at_most_k("ab", 1),
longest_substring_count_at_most_k("a", 1),
longest_substring_count_at_most_k("aabbcc", 1),
longest_substring_count_at_most_k("aabbcc", 2),
longest_substring_count_at_most_k("aabbcc", 3)
]



print("With At Most K Distinct Characters")
for case in cases:
    print(case)