395. Longest Substring with At Least K Repeating Characters

solve.py

from collections import Counter


def solve_1(s, k):
    # the one i came up with
    chars = Counter()
    start = 0
    ans = ''
    ans_len = float('-inf')

    for end in range(len(s)):
        # go right
        chars[s[end]] += 1

        # found ans
        if len(chars) <= k:
            if end-start+1 > ans_len:
                ans = s[start:end+1]
                ans_len = end-start+1

        # shorten if not valid
        while len(chars) > k:
            chars[s[start]] -= 1
            if chars[s[start]] == 0:
                chars.pop(s[start])
            start += 1
    return ans

def solve_2(s, k):
    # using a counter variable
    chars = Counter()
    start = 0
    counter = 0
    ans = 0

    for end in range(len(s)):
        # go right, increment counter if new char
        chars[s[end]] += 1
        if chars[s[end]] == 1:
            counter += 1

        # window is invalid
        while counter > k:
            # decrement count and counter if count is 0
            chars[s[start]] -= 1
            if chars[s[start]] == 0:
                counter -= 1
            start += 1
        
        # computer ans
        ans = max(ans, end-start+1)
    return ans

s = 'wallalltour'
k = 2

print(solve_1(s, k))
print(solve_2(s, k))