LeetCode 30. Substring with Concatenation of All Words

Question

You are given a string s and an array of strings words of the same length. Return all starting indices of substring(s) in s that is a concatenation of each word in words exactly once, in any order, and without any intervening characters.

You can return the answer in any order.

Example 1:

Input: s = "barfoothefoobarman", words = ["foo","bar"]
Output: [0,9]
Explanation: Substrings starting at index 0 and 9 are "barfoo" and "foobar" respectively.
The output order does not matter, returning [9,0] is fine too.

Example 2:

Input: s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
Output: []

Example 3:

Input: s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
Output: [6,9,12]

Constraints:

• 1 <= s.length <= 104
• s consists of lower-case English letters.
• 1 <= words.length <= 5000
• 1 <= words[i].length <= 30
• words[i] consists of lower-case English letters.

Source: https://leetcode.com/problems/substring-with-concatenation-of-all-words/

Solution

Sliding window with offset and step.

// search by the step of wlen
private void slidingWindow(int initLeft, int wlen, int targetSize, String s,
                           Map<String, Integer> dict, List<Integer> result) {
    // left and right are the start indexes of the first word and the last word
    // in the window respectively
    int left = initLeft, right = initLeft;
    // the number of rules need to meet
    int toMeet = dict.size();
    int slen = s.length();
    Map<String, Integer> wordCount = new HashMap<>();

    while (right <= slen - wlen) {
        String curr = s.substring(right, right + wlen);
        if (dict.containsKey(curr)) {
            wordCount.put(curr, wordCount.getOrDefault(curr, 0) + 1);
            if (wordCount.get(curr).equals(dict.get(curr))) {
                toMeet--;
            }
            while (toMeet == 0) { // exactly satisfy or beyond the demand
                if (right - left + wlen == targetSize) {
                    result.add(left);
                }
                String remove = s.substring(left, left + wlen);
                // wordCount must contain remove
                wordCount.put(remove, wordCount.getOrDefault(remove, 0) - 1);
                if (wordCount.get(remove) < dict.get(remove)) { // break one rule
                    toMeet++;
                }
                left += wlen;
            }
            right += wlen;
        } else { // encounter an invalid word
            right += wlen;
            left = right;
            toMeet = dict.size();
            wordCount.clear();
        }
    }
}

public List<Integer> findSubstring(String s, String[] words) {
    int wlen = words[0].length();
    int wnum = words.length;
    // word -> the number of times it should appear
    Map<String, Integer> dict = new HashMap<>();
    for (String word : words) {
        dict.put(word, dict.getOrDefault(word, 0) + 1);
    }

    List<Integer> result = new ArrayList<>();
    // for each initial offset
    for (int i = 0; i < wlen; i++) {
        slidingWindow(i, wlen, wnum * wlen, s, dict, result);
    }
    return result;
}