LeetCode 30.

Question

You are given a string s and an array of strings words. All the strings of words are of the same length.

A concatenated string is a string that exactly contains all the strings of any permutation of words concatenated.

For example, if words = ["ab","cd","ef"], then "abcdef", "abefcd", "cdabef", "cdefab", "efabcd", and "efcdab" are all concatenated strings. "acdbef" is not a concatenated string because it is not the concatenation of any permutation of words.
Return an array of the starting indices of all the concatenated substrings in s. You can return the answer in any order.

Example

Example 1:

Input: s = “barfoothefoobarman”, words = [“foo”,”bar”]

Output: [0,9]

Explanation:

The substring starting at 0 is “barfoo”. It is the concatenation of [“bar”,”foo”] which is a permutation of words. The substring starting at 9 is “foobar”. It is the concatenation of [“foo”,”bar”] which is a permutation of words.

Example 2:

Input: s = “wordgoodgoodgoodbestword”, words = [“word”,”good”,”best”,”word”]

Output: []

Explanation:

There is no concatenated substring.

Example 3:

Input: s = “barfoofoobarthefoobarman”, words = [“bar”,”foo”,”the”]

Output: [6,9,12]

Explanation:

The substring starting at 6 is “foobarthe”. It is the concatenation of [“foo”,”bar”,”the”]. The substring starting at 9 is “barthefoo”. It is the concatenation of [“bar”,”the”,”foo”]. The substring starting at 12 is “thefoobar”. It is the concatenation of [“the”,”foo”,”bar”].

Intuition

Even I know this problem can be solved by Sliding Window, it’s complicated.

The following is my trial and yours is probably better than this so just give it a look :D

I first tried delcare an array to record which word in words had been visited and use Queue to record the index.

However, this solution pass over 80% testcases but will be failed on duplicate words.

Then, I tried use HashMap to keep the numbers of each word and use Queue to make sure FIFO.

Approach

Delcare two variables to record temporary data:

• Queue: keep current consecutive included words in a sequence

• Map: keep usable number of words

It comes in three sitautions:

• (1) If current portion is not the key in Map, clear the queue and reset the map (reset words we can use)
• (2) If current portion matches the key but the number is not enough, poll out the queue while the usable number added by one until enough
• (3) If current portion matches the key and the number is enough, add portion to the queue and the matched number minus one

Afterwards:

• (RESULT) If Queue size is equal to the length of array words, meaning the substring(multiple portion concatenated) is existed, record the result and poll out the queue once (because portion[1] to portion[n] is still qualified)

Take Exmaple 1 to explain how my solution works:

Input: s = “barfoothefoobarman”, words = [“foo”,”bar”]

• init: i=0, j=0, Queue=[], Map=[“foo”,”bar”]=>[1, 1], RESULT=[]
• i=0, j=3, portion=substring(0, 3)=”bar” => (3) => Queue=[“bar”], Map=[“foo”,”bar”]=>[1, 0]
• i=0, j=6, portion=substring(3, 6)=”foo” => (3) => Queue=[“bar”, “foo”], Map=[“foo”,”bar”]=>[0, 0]
• (RESULT) => Queue=[“foo”], Map=[“foo”,”bar”]=>[0, 1], RESULT=[0]
• i=0, j=9, portion=substring(6, 9)=”the” => (1) => Queue=[], Map=[“foo”,”bar”]=>[1, 1]
• i=0, j=12, portion=substring(9, 12)=”foo” => (3) => Queue=[“foo”], Map=[“foo”,”bar”]=>[0, 1]
• i=0, j=15, portion=substring(12, 15)=”bar” => (3) => Queue=[“foo”, “bar”], Map=[“foo”,”bar”]=>[0, 0]
• (RESULT) => Queue=[“bar”], Map=[“foo”,”bar”]=>[1, 0], RESULT=[0, 9]
• i=0, j=18, portion=substring(15, 18)=”man” => (1) => Queue=[], Map=[“foo”,”bar”]=>[1, 1]
• i=1, …

Complexity

• Time complexity: O(wlen * slen)

  wlen: length of array words

  slen: length of s

• Space complexity: O(n)

Code

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        int wlen = words[0].length();
        Queue<String> queue = new LinkedList<>();
        Map<String, Integer> map = new HashMap<String, Integer>();
        Map<String, Integer> copy = new HashMap<String, Integer>();
        for (String w: words) {
            if (map.containsKey(w)) {
                map.put(w, map.get(w) + 1);
                copy.put(w, copy.get(w) + 1);
            }else{
                map.put(w, 1);
                copy.put(w, 1);
            }
        }
        List<Integer> result = new ArrayList<>();

        for (int i=0; i<wlen; i++) { //wlen
            for (int j=i; j<=s.length()-wlen; j+=wlen) { //slen / wlen
                String portion = s.substring(j, j+wlen);
                int index = map.getOrDefault(portion, -1);
                if (index < 0) {
                    queue.clear();
                    map.clear();
                    map.putAll(copy);
                    continue;
                }else if (index == 0) { //consumed
                    while (queue.size() > 0) {
                        String back = queue.peek();
                        if (back.equals(portion)) {
                            queue.poll();
                            queue.offer(portion);
                            break;
                        }else{
                            map.put(back, map.get(back) + 1);
                            queue.poll();
                        }
                    }
                    continue;
                }
                // matched
                queue.offer(portion);
                map.put(portion, map.get(portion) - 1);
                if (queue.size() == words.length) {
                    String back = queue.poll();
                    map.put(back, map.get(back) + 1);
                    result.add(j - queue.size() * wlen);
                }
            }
            queue.clear();
            map.clear();
            map.putAll(copy);
        }
        return result;
    }
}

Check out the description of this problem at LC 30.