Substring with Concatenation of All Words

This page explains Java solution to problem Substring with Concatenation of All Words using HashMap.

Problem Statement

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.

Input: s = "barfoothefoobarman", words = ["foo","bar"]
Output: [0,9]

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

Solution

package com.vc.hard;

import java.util.*;

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

        HashMap<String, Integer> mapInitial = new HashMap<>();
        int required = 0;
        for(String word: words) {
            mapInitial.put(word, mapInitial.getOrDefault(word, 0) + 1);
            required++;
        }

        int wordLength = words[0].length();
        for(int i = 0; i + words.length * wordLength <= s.length(); i++) {
            HashMap<String, Integer> map = new HashMap<>();

            int total = 0;
            for(int j = i; j <= i + words.length * wordLength; j = j + wordLength) {
                //Fixed length word
                String word = s.substring(j, j + wordLength);

                //See if word is present in a words input array
                map.put(word, map.getOrDefault(word, 0) + 1);
                if(map.get(word) > mapInitial.getOrDefault(word, 0)) break;

                //If so see if we found all the elements in a input words array
                if(++total == required) {
                    res.add(i);
                    break;
                }
            }
        }
        return res;
    }
}

Time Complexity

O(N * M * K) Where
N number of elements in an input string
M length of word in words input array
K number of elements in words input array

Space Complexity

O(K) to store K elements from words input array into HashMap