Substring with Concatenation of All Words

 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.

Solution:

public static List<Integer> findSubstring(String s, String[] words) {

		HashMap<String, Integer> hashMap = new HashMap<String, Integer>();

		ArrayList<Integer> index = new ArrayList<Integer>();

		int wordSize = words[0].length();

		int totalNoOfWords = words.length;

		int sizeOfWords = wordSize * totalNoOfWords;

		int n = s.length();

		if (sizeOfWords > n) {
			return index;
		}

		for (String word : words) {
			hashMap.put(word, hashMap.getOrDefault(word, 0) + 1);
		}

		for (int i = 0; i <= n - sizeOfWords; i++) {
			HashMap<String, Integer> tempMap = new HashMap<String, Integer>(hashMap);
			int j = i;
			int count = totalNoOfWords;

			while (j < i + sizeOfWords) {

				String word = s.substring(j, j + wordSize);

				if (!hashMap.containsKey(word) || tempMap.get(word) == 0) {
					break;
				} else {
					tempMap.put(word, tempMap.get(word) - 1);
					count--;
				}
				j = j + wordSize;
			}

			if (count == 0) {
				index.add(i);
			}

		}
		return index;
	}

	public static void main(String[] args) {
		String s = "wordgoodgoodgoodbestword";
		String[] words = new String[] { "word", "good", "best", "good" };

//		s = "barfoofoobarthefoobarman";
//		words = new String[] { "bar", "foo", "the" };

//		s = "barfoothefoobarman";
//		words = new String[] { "foo", "bar" };

		findSubstring(s, words);
	}

Thanks for reading :) 

Whether this post is helpful?

Have something to add to this post? If you have any other quick thoughts/hints that you think people will find useful? Share it in the comments. feedback are welcome...