30. Substring with Concatenation of All Words

LeetCode
,

Sliding Window

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> result = new ArrayList<>();
        if (s == null || s.length() == 0 || words == null || words.length == 0)
            return result;

        int wordLen = words[0].length();
        int wordCount = words.length;
        int totalLen = wordLen * wordCount;

        // create frequency map
        Map<String, Integer> wordMap = new HashMap<>();
        for (String word : words) {
            wordMap.put(word, wordMap.getOrDefault(word, 0) + 1);
        }

        // try each offset within a word length (like abc***, *abc**, **abc*)
        for (int i = 0; i < wordLen; i++) {
            int left = i, right = i;
            Map<String, Integer> seen = new HashMap<>();
            int count = 0;

            while (right + wordLen <= s.length()) {
                String word = s.substring(right, right + wordLen);
                right += wordLen;

                if (wordMap.containsKey(word)) {
                    seen.put(word, seen.getOrDefault(word, 0) + 1);
                    count++;

                    while (seen.get(word) > wordMap.get(word)) {
                        // too much word!
                        String leftWord = s.substring(left, left + wordLen);
                        // update the word in seen, remove 1 time of the left word
                        seen.put(leftWord, seen.get(leftWord) - 1);
                        left += wordLen;
                        count--;
                    }

                    if (count == wordCount) {
                        result.add(left);
                    }

                } else {
                    seen.clear();
                    count = 0;
                    left = right;
                }
            }

        }

        return result;
    }
}

Remarks:

  1. TC: $O(nk)$ (n=s.length(), k=words.length, wl=wordLen)

    Most outer loop, we check $wl$ times; at most move the window $n/wl$ times ;In one sliding window, we operate $k$ times. $wl\cdot n/wl \cdot k = nk$

  2. Java Map method: map.getOrDefault(item, defaultNumber)

  3. Set to Mappings, to compare the times of word in the wordlist and the time of appears in the current sequence.