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)

the way to conquer this problem is to enumerate on the dict word to be removed from original string and bfs through, maintain a minLength. we have to try every words in the diction in each iteration

public class Solution {
    /**
     * @param s a string
     * @param dict a set of n substrings
     * @return the minimum length
     */
    public int minLength(String s, Set<String> dict) {
        // Write your code here

        if (dict == null || dict.size() == 0) {
            return 0;
        }

        Queue<String> queue = new LinkedList<>();
        HashSet<String> isVisited = new HashSet<>();
        queue.add(s);
        isVisited.add(s);

        int minLength = s.length();

        while (!queue.isEmpty()) {
            String cur = queue.poll();
            for (String sub : dict) {
                int index = cur.indexOf(sub);
                while (index != -1) {
                    //caab aa
                    String newString = cur.substring(0, index) + cur.substring(index + sub.length(), cur.length());

                    if (!isVisited.contains(newString)) {
                        queue.offer(newString);
                        isVisited.add(newString);
                        minLength = Math.min(minLength, newString.length());    
                    }
                    index = cur.indexOf(sub, index + 1);
                }
            }
        }

        return minLength;
    }



    //ccdaabcdbb -> ccda{ab}cdbb -> c {cd} a {cd} bb -> c{ab}b
    //ccdaabcdbb -> c {cd} aab {cd} bb -> ca{ab]bb -> c {ab} b
    //aabbccdd
    //{bc, ad}
}