Given a stringsand a set ofnsubstrings. You are supposed to remove every instance of those n substrings from s so that s is of the minimum length and output this minimum length.

Have you met this question in a real interview?

Yes

Example

Given s =ccdaabcdbb, substrs =["ab", "cd"]
Return2

Explanation:
ccdaabcdbb->ccdacdbb->cabb->cb(length = 2)

class Solution {
public:
    /**
     * @param s a string
     * @param dict a set of n substrings
     * @return the minimum length
     */
    int minLength(string& s, set<string>& dict) {
        // Write your code here
        queue<string> q;
        set<string> hash;

        q.push(s);
        hash.insert(s);
        int minLen = s.length();

        while (!q.empty()) {
            string tmp = q.front(); q.pop();
            for (const string& substr : dict) {
                int index = 0;
                while ((index = tmp.find(substr, index)) != string::npos) {
                    string newStr = tmp.substr(0, index) + 
                                    tmp.substr(index + substr.length());
                    index += 1;
                    if (hash.find(newStr) != hash.end()) {
                        continue;
                    }
                    if (newStr.size() < minLen) {
                        minLen = newStr.size();
                    }
                    q.push(newStr);
                    hash.insert(newStr);
                }
            }
        }

        return minLen;
    }
};