extraCharacters.txt

2707. Extra Characters in a String

You are given a 0-indexed string s and a dictionary of words dictionary.
You have to break s into one or more non-overlapping substrings such that each substring is present in dictionary. 
There may be some extra characters in s which are not present in any of the substrings.
Return the minimum number of extra characters left over if you break up s optimally.

class Solution {
public:
    int minExtraChar(string s, vector<string>& dictionary) {
        unordered_set<string> dic;
        int length = s.length();
        for(auto i : dictionary){
            dic.insert(i);
        }
        vector<int> delCount(length+1);
        for(int j = 1 ; j <= length ; j++){
            delCount[j] = 1 + delCount[j - 1];
            for(int k = j ; k > 0 ; k--){
                string word = s.substr(k-1,j-k+1);
                if(dic.count(word)){
                    delCount[j] = min(delCount[j], delCount[k-1]);
                }
            }
        }

        return delCount[length];
    }
};