<p>You are given a <strong>0-indexed</strong> string <code>s</code> and a dictionary of words <code>dictionary</code>. You have to break <code>s</code> into one or more <strong>non-overlapping</strong> substrings such that each substring is present in <code>dictionary</code>. There may be some <strong>extra characters</strong> in <code>s</code> which are not present in any of the substrings.</p>

<p>Return <em>the <strong>minimum</strong> number of extra characters left over if you break up </em><code>s</code><em> optimally.</em></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;leetscode&quot;, dictionary = [&quot;leet&quot;,&quot;code&quot;,&quot;leetcode&quot;]
<strong>Output:</strong> 1
<strong>Explanation:</strong> We can break s in two substrings: &quot;leet&quot; from index 0 to 3 and &quot;code&quot; from index 5 to 8. There is only 1 unused character (at index 4), so we return 1.

</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;sayhelloworld&quot;, dictionary = [&quot;hello&quot;,&quot;world&quot;]
<strong>Output:</strong> 3
<strong>Explanation:</strong> We can break s in two substrings: &quot;hello&quot; from index 3 to 7 and &quot;world&quot; from index 8 to 12. The characters at indices 0, 1, 2 are not used in any substring and thus are considered as extra characters. Hence, we return 3.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 50</code></li>
	<li><code>1 &lt;= dictionary.length &lt;= 50</code></li>
	<li><code>1 &lt;= dictionary[i].length &lt;= 50</code></li>
	<li><code>dictionary[i]</code>&nbsp;and <code>s</code> consists of only lowercase English letters</li>
	<li><code>dictionary</code> contains distinct words</li>
</ul>

class Solution {
public:
    class Trie {
    public:
        vector<std::shared_ptr<Trie>> children = vector<std::shared_ptr<Trie>>(26);
        int wordCount = 0;
        int len = 0;
    };

    int minExtraChar(string s, vector<string>& dictionary) {
        dp = vector<int>(s.size() + 1, -1);
        dp[s.size()] = 0;
        for (const auto& word : dictionary) {
            insert(word);
        }

        return breakdown(s, 0);
    }

private:
    std::shared_ptr<Trie> root = std::make_shared<Trie>();
    vector<int> dp;

    void insert(const string& word) {
        auto current = root;
        int len = 0;

        for (const char c : word) {
            int key = c - 'a';
            if (current->children[key] == nullptr) {
                current->children[key] = std::make_shared<Trie>();
            }
            current = current->children[key];
            ++len;
        }

        ++current->wordCount;
        current->len = len;
    }

    vector<int> find(const string& word) {
        auto current = root;
        //int maxLen = 0;
        vector<int> result;

        for (const char c : word) {
            int key = c - 'a';
            if (current->children[key] == nullptr) {
                return result;
                //return maxLen;
            }
            current = current->children[key];
            //maxLen = std::max(maxLen, current->len);
            if (current->len > 0) {
                result.emplace_back(current->len);
            }
        }

        return result;
    }

    int breakdown(const string& s, int pos) {
        int count = 0;
        int len = 0;
        vector<int> lenghts;
        if(dp[pos] >= 0) {
            return dp[pos];
        }

        //std::cout << "==================================================" << std::endl;
        //std::cout << "s = " << s.substr(pos) << std::endl;
        int minCount = INT_MAX;
        minCount = min(minCount, breakdown(s, pos + 1)) + 1;

        lenghts = find(s.substr(pos));
        for (const int len : lenghts) {
            //std::cout << pos << ", " << count << ", " << len << std::endl;
            //std::cout << s.substr(pos + count) << std::endl;
            minCount = min(minCount, breakdown(s, pos + len));
        }

        count += minCount;


        dp[pos] = count;
        return dp[pos];
    }
};

/*
["ae", "anoni", "at", "bqqb", "c", "ce", "ctsxk", "cujh", "encgp", "ensv", "g", "gb", "gn", "gv",
 "hnk", "jr", "jljuo", "ka", "kk", "kumr", "lgrhy", "mppc", "mxhmv", "o", "ohk", "qafkx",
  "r", "rwrpq", "t", "tze", "ujjd", "ugn", "uy", "uzbc", "vl", "vv", "xdye", "x", "xn", "xqkgj",
  "yf", "yzbe", "zdzz", "zkowk", "zqpn", "zxhg"]
*/
152560