30. Substring with Concatenation of All Words

Link

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

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: []

Solution

TimeComplexitiy : O(n) where n is the s.length

SpaceComplexity: O(m), where m is words.length

  public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> ret = new ArrayList<>();
        if (words.length == 0)
            return ret;

        HashMap<String, Integer> map = new HashMap<>();
        for (String word : words) {
            map.put(word, map.getOrDefault(word, 0) + 1);
        }
        int wordLength = words[0].length();
        int count = words.length;
        int minSize = count * wordLength;
        for (int i = 0; i <= s.length() - minSize; i++) {
            int j = 0;
            HashMap<String, Integer> seens = (HashMap<String, Integer>) map.clone();
            while (j < count) {
                String target = s.substring(i + j * wordLength, i + (j * wordLength) + wordLength);
                if (seens.containsKey(target)) {
                    if (seens.get(target) > 0) {
                        seens.put(target, seens.get(target) - 1);
                    } else {
                        break;
                    }
                } else {
                    break;
                }
                j++;
                if (count == j) {
                    ret.add(i);
                }
            }
        }
        return ret;
    }