39. Substring with Concatenation of All Words

Topic :

hashing

Difficulty :

hard

Problem Link :

problem statement

You are given a string s and an array of strings words. All the strings of words are of the same length.

A concatenated substring in s is a substring that contains all the strings of any permutation of words concatenated.

For example, if words = ["ab","cd","ef"], then "abcdef", "abefcd", "cdabef", "cdefab", "efabcd", and "efcdab" are all concatenated strings. "acdbef" is not a concatenated substring because it is not the concatenation of any permutation of words.

Return the starting indices of all the concatenated substrings in s. You can return the answer in any order

Example 1:

Input: s = "barfoothefoobarman", words = ["foo","bar"]
Output: [0,9]
Explanation: Since words.length == 2 and words[i].length == 3, 
the concatenated substring has to be of length 6.
The substring starting at 0 is "barfoo".
It is the concatenation of ["bar","foo"] which is a permutation of words.
The substring starting at 9 is "foobar". 
It is the concatenation of ["foo","bar"] which is a permutation of words.
The output order does not matter. Returning [9,0] is fine too.

Example 2:

Input: s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
Output: []
Explanation: Since words.length == 4 and words[i].length == 4,
the concatenated substring has to be of length 16.
There is no substring of length 16 is s 
that is equal to the concatenation of any permutation of words.
We return an empty array.

Example 3:

Input: s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
Output: [6,9,12]
Explanation: Since words.length == 3 and words[i].length == 3, 
the concatenated substring has to be of length 9.
The substring starting at 6 is "foobarthe". 
It is the concatenation of ["foo","bar","the"] which is a permutation of words.
The substring starting at 9 is "barthefoo".
It is the concatenation of ["bar","the","foo"] which is a permutation of words.
The substring starting at 12 is "thefoobar". 
It is the concatenation of ["the","foo","bar"] which is a permutation of words.

Constraints:

1 <= s.length <= 104
1 <= words.length <= 5000
1 <= words[i].length <= 30
s and words[i] consist of lowercase English letters.

solution

import java.io.*;
import java.util.*; 
class Substring_with_Concatenation_of_All_Words
{
    public static void main(String args[]){
        String s="barfoothefoobarman";
        String[] words={"foo","bar"};
        System.out.println(findSubstring(s,words));
    }
    static List<Integer> findSubstring(String s, String[] words) {
        List<Integer> res= new ArrayList<Integer>();
        HashMap<String,Integer> map_countWords=new HashMap<>();
        
        for(String word : words)
        map_countWords.put(word,map_countWords.getOrDefault(word,0)+1);
        
        int wordLength=words[0].length(); // length of each word in words array
        int numberOfWords=words.length;// total no.of words in word array
        int substringLength= wordLength*numberOfWords; //length of apt substring
        
        // check for all substrings of length substringLength 
        for(int i=0;i<=s.length()-substringLength;i++){
            String sub=s.substring(i,i+substringLength);
            if(isConcat(sub,map_countWords,wordLength))//check if it is a valid substring
                res.add(i);   //add it to the resut if it is a valid substring
        }
        
        return res;
    }
    
    static boolean isConcat(String sub, HashMap<String,Integer> map_countWords,int wordLength){
       
        HashMap<String,Integer> map_seen=new HashMap<String,Integer>();
        //check for every word of length "wordLength"
        for(int i=0;i<=sub.length()-wordLength;i+=wordLength){
            String tempWord=sub.substring(i,i+wordLength);
            map_seen.put(tempWord,map_seen.getOrDefault(tempWord,0)+1);//put the words in the the map along with their frequency
        }
        
        return map_seen.equals(map_countWords);// if both the maps are similar then it is a valid substring        
    }
}