Longest K Unique Characters Substring

Given a string you need to print the size of the longest possible substring that has exactly k unique characters. If there is no possible substring print -1.

Example

For the string aabacbebebe and k = 3 the substring will be cbebebe with length 7.

Specifically, there are three unique characters (c, b, and e) and they create a substring of length 7.

We assume that we aren't reordering the string.

S='aabacbebebe'

k=3
longest=-1    # keep record of the longest
start=0       # start of the current substring being evaluated
chars=set()   # keep a record of characters that we've seen

def update_longest(start, end, S, longest):
    contender = S[start:end]
    if longest == -1:
        return contender
    if len(contender) > len(longest):
        longest=contender
    print('New longest is %s' %longest)
    return longest


for idx in range(len(S)):
    s = S[idx]

    # The character is in the current substring
    if s in chars:
        print('%s is in %s, continuing' %(s, chars))
        longest = update_longest(start, idx, S, longest)
    else:
        # S isn't one of the characters, and we are at stopping point
        if len(chars) == k:
            print('final evaluation of %s,%s' %(s, chars))
            longest = update_longest(start, idx, S, longest)
            start=idx
            chars=set(s)
        else:
            chars.add(s)
            longest = update_longest(start, idx, S, longest)
            print('added %s,%s' %(s, chars))

vsoch/README.md

Longest K Unique Characters Substring

Example