# Former Coding Interview Question:
# Find longest word in dictionary that is a subsequence of a given string

# 2nd Solution O(N+L), where N is length of base word and L sum of words length

from collections import defaultdict


S = "abppplee"
D = {"able", "ale", "apple", "bale", "kangaroo"}

def longest_subsequence(words, base):
    found = []
    # Create map array
    map = defaultdict(list)
    
    index = 0
    # Iterate words
    for word in words:
        # Check if word is not None
        if word != "":
            # Split words into map by first character
            map[word[0]].append((word, 0))

    # While we're not out of base word
    while index < len(base):
        # Find all tuples containing suitable letter
        for word_tuple in map[base[index]][:]:
            # Create new tuple with incremented index
            new_tuple = (word_tuple[0], word_tuple[1] + 1)

            # Remove tuple from list
            map[base[index]].remove((word_tuple[0], word_tuple[1]))

            # If whole word in tuple was checked it is subsequence
            if new_tuple[1] == len(new_tuple[0]):
                found.append(new_tuple[0])
            # If not, just move it to proper list
            else:
                tuples_word = new_tuple[0]
                letter = tuples_word[new_tuple[1]]
                map[letter].append(new_tuple)
        index += 1

        # Find longest string in found
        longest_length = 0
        longest_word = ""
        for word in found:
            if (len(word) > longest_length):
                longest_word = word
    return longest_word

print(longest_subsequence(D, S))
        
    
    
