<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:
    int solve(int index , string s , unordered_map<string , int> mp , vector<int> &dp){

        if(index>=s.size()){
            return 0;
        }
        if(dp[index]!=-1){
            return dp[index];
        }


        string currStr = "";
        int minwords = s.size();
        for(int i=index;i<s.size();i++){

            currStr.push_back(s[i]);
            int currWords = 0;
            if(!mp.count(currStr)){
                currWords = currStr.length();
            }

            int extraWords = solve(i+1 , s , mp , dp);
            int totalwods = currWords + extraWords;
            
            minwords = min(minwords , totalwods);


        }
            

        return dp[index] =  minwords;

    }
    int minExtraChar(string s, vector<string>& dictionary) {
        

        // // unordered_map<char , bool> mp;
        // vector<bool> v(s.length() , false);

        // for(auto &word:dictionary){

        //     int n = word.length();
        //     int i=0;
        //     int j=0;
        //     // cout<<word<<" ";
        //     while(j<s.length()){
                
        //         if(j-i+1 < n){
        //             j++;
        //         }
        //         else if(j-i+1 == n){
        //             // cout<<j-i+1<<" ";
        //             string sub = s.substr(i , j-i+1);
        //             // cout<<sub<<" ";
        //             if(sub == word){
        //                 for(int k=i;k<=j;k++){
        //                     v[k] = true;
        //                 }
        //                 break;
        //             }
        //             i++;
        //             j++;
        //         }
        //     }
        // }
        // int ans = 0;
        // for(int i=0;i<v.size();i++){
        //     if(v[i] == false){
        //         ans++;
        //     }
        // }

        // return ans;





    // using DP 
    //         Hint:

    // We know that substring of s must exist in dictionary to be able to break. The substring may start from index 0. If it doesn't then the index 0 is the leftover and so on.

    // More generally, for every substring there are a 2 choices:

    // this substring is an leftover then len(substring) + mininmumLeftOver(rest of the string)
    // this substring is part of a substring of string from dictionary, then 0(no leftover) + mininmumLeftOver(rest of the string).
    // We shall pick the minimum from these 2 choices.



    // bhai simple ha .. dekh M samjata hu kya chal rah ha recursion mai ...... lets take 3 cases -> solve(0 , s , mp) , solve(3 , s , mp) and solve(8 , s , mp) ...... now in solve(8 , s , mp) .. the string starts from world .... and by resuisive calls for 8+1 ...etc .. the world breaks in substring like -> w , wo , wor , o , or and so like that .. and at last substring world will be found in mp .. which set currwords to 0 and we have to return .. so solve(8 , s , mp) .. will return 0 ..... similary -> solve(3 , s , mp) .. s will  be => helloworld .. the hello susbtring will be found in mp which set currword = 0 .. .. so it will also return 0 ...so the remaining solve(0 , s , mp) ... will return 3 as say is not in mp ........


    // by chatgtp

//     Combining Results
// Let's combine the results:

// From solve(8, "sayhelloworld", mp):

// The recursive call returns 0 (base case). Since "world" is in the dictionary, currWords = 0.
// The minimum number of extra characters from index 8 is 0.
// From solve(3, "sayhelloworld", mp):

// The recursive call returns 0 (base case). Since "hello" is in the dictionary, currWords = 0.
// The minimum number of extra characters from index 3 is 0.
// From solve(0, "sayhelloworld", mp):

// The recursive call returns 0 (base case). "say" is not in the dictionary, currWords = 3.
// The minimum number of extra characters from index 0 is 3.
// Conclusion
// The minimum number of extra characters left after breaking the string s = "sayhelloworld" using words from the dictionary ["hello", "world"] is 3, corresponding to the substring "say", which is not in the dictionary.



    // T.C - > Time complexity:O(nnm)
// Space complexity:O(k * m + n).

    // unordered_map<string,int> mp;
    // for(auto &i:dictionary){
    //     mp[i]++;
    // }
    
    // vector<int> dp(s.size()+1 , -1);
    // return solve(0 , s , mp , dp);



    // using tabulation
    int n = s.size();
    unordered_map<string ,int> mp;

    for(string &i:dictionary){
        mp[i]++;
    }

    vector<int> dp(n+1 , 0);

    for(int index = n-1 ;index>=0;index--){

        string currStr = "";
        int minExtra = s.size();
        for(int cutIdx = index;cutIdx < n;cutIdx++){
            currStr.push_back(s[cutIdx]);
                
                int currExtra = (mp.count(currStr))? 0 : currStr.size();
                int nextExtra = dp[cutIdx + 1]; 
                int totalExtra = currExtra + nextExtra;

                minExtra = min(minExtra, totalExtra);
        }
        dp[index] = minExtra;
    }



        return dp[0];

    }
};
71124