class TrieNode:
    def __init__(self):
        self.children = {}
        self.end_of_the_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        node = self.root
        for c in word:
            if c not in node.children:
                node.children[c] = TrieNode()
            node = node.children[c]
        node.end_of_the_word = True

class Solution:
    def minExtraChar(self, s, words):
        # gen Trie with <words>
        t = Trie()
        for word in words:
            t.insert(word)

        # while left pointer less than the end of the <s>,
        # check all substrings
        l = 0
        found_words_len = 0
        l_need_to_jump = False
        while l < len(s):
            node = t.root
            for p in range(l, len(s)):
                c = s[p]
                if c not in node.children:
                    break
                node = node.children[c]
                if node.end_of_the_word:
                    word_len = p - l + 1
                    found_words_len += word_len
                    # jump left pointer, so we don't check overlapping chars
                    l_need_to_jump = True
                    l = p + 1
            if l_need_to_jump:
                l_need_to_jump = False
                # continue with already jumped left pointer
            else:
                # haven't found any new words, continue checking all substrings one by one
                l += 1
        return len(s) - found_words_len