# class TrieNode:
#     def __init__(self):
#         self.children = {}  # Represents each character of the alphabet.
#         self.isEnd = False  # To determine if the current TrieNode marks the end of a word.
class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insertword(self, word):
        cur = self.root
        for c in word:
            if c not in cur.children:
                cur.children[c] = TrieNode()
            cur = cur.children[c]
        cur.isEnd = True

class Solution:
    def minExtraChar(self, s, dictionary):
        # Make the tree
        trie = Trie()

        # Build the tree
        for word in dictionary:
            trie.insertword(word)

        # pointers for current word and extra chars
        curword,extras,c = 0,0,0

        # set current node to traverse the tree
        cur = trie.root

        # one loop through the string
        while c < len(s)::
            if s[c] not in cur.children:
                extras += curword
                if curword == 0:
                    c += 1
                    extras += 1
                curword = 0
                cur = trie.root

            else:
                cur = cur.children[c] # advance pointer

                curword += 1

                # if its the end of a word, we dont need to add the word to extras
                if cur.isEnd:
                    cur = trie.root
                    curword = 0
                c += 1

        return extras