GeetCode Hub

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.

class Solution { public List<Integer> findSubstring(String s, String[] words) { List<Integer> ans = new ArrayList<Integer>(); if(s==null || words.length==0){ return ans; } int wordLen = words[0].length(); int len = s.length(); HashMap<String, Integer> count = new HashMap<String, Integer>(); for(int i=0;i<words.length;i++){ count.put(words[i], count.getOrDefault(words[i],0)+1); } for(int i=0;i<len-wordLen+1;i++){ int start = i; int curr = i; HashMap<String, Integer> copy = new HashMap<String, Integer>(count); while(curr+wordLen < len+1){ String currWord = s.substring(curr,curr+wordLen); if(copy.containsKey(currWord)){ copy.put(currWord, copy.get(currWord)-1); if(copy.get(currWord)==0){ copy.remove(currWord); } if(copy.size()==0){ ans.add(start); break; } curr += wordLen; } else{ break; } } } return ans; } }

This question requires the knowledge of sliding window approach. If we keep track of what are the words available in the word list along with it's count and use them one by one, then by sliding window technique we can easily solve this question. A detailed analysis is provided in the Video.

Time Complexity: O(n*(l*m)) // where n is the length of string and l is the number of words in wordlist and m is the length of each word.

Space Complexity: O(l*m) // where l is the number of words in the wordlist and m is the length of each word.