Given a string, find the length of the longest substring in it with no more than K distinct characters.

longest_substring_with_k_distinct.py

def longest_substring_with_k_distinct(str, k):
  windowStart = 0
  uniqueCharacterCount = {}
  longestRun = 0
  currentRun = 0
  uniqueCharacters = 0
  for windowEnd in range(len(str)):
    nextCharacter = str[windowEnd]
    nextCharacterCount = uniqueCharacterCount.get(nextCharacter)
    # We have seen this character already to increment its count
    if nextCharacterCount is None:      
      uniqueCharacterCount.update({nextCharacter:1})
      print('Added ' + nextCharacter + ' to the count ', currentRun)
      currentRun += 1
      uniqueCharacters +=1
      
    else:
      nextCharacterCount+=1
      uniqueCharacterCount.update({nextCharacter: nextCharacterCount})
      print('Added ' + nextCharacter + ' to the count ', currentRun)
      currentRun += 1
      

    # while greater than k, remove from start window until less than k
    # decrement current run
    while uniqueCharacters > k:
      outOfWindowCharacter = str[windowStart]
      print('Out of window char: ', outOfWindowCharacter)
      outOfWindowCount = uniqueCharacterCount[outOfWindowCharacter]
      if outOfWindowCount == 1:
        del uniqueCharacterCount[outOfWindowCharacter]
        currentRun -= 1
        uniqueCharacters -=1
      else:
        outOfWindowCount -=1
        currentRun -= 1
        uniqueCharacterCount.update({outOfWindowCharacter: outOfWindowCount})
      windowStart +=1

    # if current run is greater than longest run, set longest run to current run
    if currentRun > longestRun:
        longestRun = currentRun
  print()
  return longestRun

def main():
  print("Length of the longest substring: " + str(longest_substring_with_k_distinct("araaci", 2)))
  print("Length of the longest substring: " + str(longest_substring_with_k_distinct("araaci", 1)))
  print("Length of the longest substring: " + str(longest_substring_with_k_distinct("cbbebi", 3)))


main()