Substring With Concatenation Of All Words

Difficulty Level Hard
Frequently asked in Amazon DE Shaw
Hashing String Two PointerViews 2466

In substring with the concatenation of all words problem, we have given a string s and a list consist of many words each of the same length. Print the starting index of the substring which can be the result of the concatenation of all the words in the list in any order.

Explanation for Substring With Concatenation Of All Words

Let the string s = “capcodthecodcap” and the given list L = [“cap”, “cod”]

Concatenate all the words of the given list. All the possible combinations of the concatenate all the words of the given list are –

  • capcod
  • codcap

Now, search the starting index of the concatenated strings in the given string.

Starting index of the substring “capcod” in the given string “capcodthecodcap” is 0.

Starting index of the substring “codcap” in the given string “capcodthecodcap” is 9.

Therefore, the output will be 0 and 9.

Example

Input: 

s = “capcodthecodcap”

L = [“cap”, “cod”]

Output:

0 9

Input: 

s = “heythejenna”

L = [“hey”, “the”]

Output:

0

Algorithm

  1. Initialize a string s of length n and a list of the words of the same length as that of the given string.
  2. Initialize a map and a temporary map.
  3. Aftet that, traverse through all possible substrings of the length equal to the concatenation of all words of the given list.
  4. Link the new map with the old map using all the possible substrings.
  5. Check if the words of the substring are present in the new map, decrement the count by 1, else break the loop.
  6. Traverse through the new map and check if the count of all words is less than 0, return the list/array res.
  7. Traverse through the returned list/array and print all the values stored in it.

C++ Program to find substring with concatenation of all words

#include <bits/stdc++.h> 
using namespace std; 
  
vector<int> Substring(string s, const vector<string>& L){ 
  
    int size = L[0].size(); 
  
    int count = L.size(); 
  
    int length = size * count; 
  
    vector<int> res; 
  
    if(length>s.size()) 
        return res; 
  
    unordered_map<string, int> hash_map; 
  
    for(int i=0; i<count; i++)  
        hash_map[L[i]]++;     
  
    for(int i=0; i<=s.size()-length; i++) { 
        unordered_map<string, int> temp_hash_map(hash_map); 
  
        int j = i,c=count; 
  
        while(j<i+length){ 
  
            string word = s.substr(j, size); 
  
  
            if(hash_map.find(word) == hash_map.end()||temp_hash_map[word]==0) 
                break; 
  
            else{ 
                temp_hash_map[word]--;
                c--;
            }  
            j += size; 
        } 
       
        if(c == 0) 
            res.push_back(i); 
    } 
  
    return res; 
} 
  
int main(){ 
    string s = "capcodthecodcap"; 
    vector<string> L = { "cap", "cod" }; 
    vector<int> indices = Substring(s, L); 
    for(int i=0; i<indices.size(); i++) 
        cout<<indices[i]<<" "; 
    return 0; 
}
0 9

Java Program to find substring with concatenation of all words

import java.util.ArrayList; 
import java.util.Arrays; 
import java.util.HashMap; 
import java.util.List;

class sub{
    
    public static ArrayList<Integer>Substring(String s, final List<String> L){ 
  
        int size = L.get(0).length(); 
         
        int count = L.size(); 
  
        int length = size * count; 
  
        ArrayList<Integer> res = new ArrayList<Integer>(); 
        int n = s.length(); 
          
        if(length > n){ 
            return res; 
        } 
  
        HashMap<String, Integer> hashMap = new HashMap<String, Integer>(); 
  
        for(String word : L){ 
            hashMap.put(word, hashMap.getOrDefault(word, 0) + 1); 
        } 
  
          
        for(int i=0; i<=n-length; i++){ 
            HashMap<String, Integer> tempMap = (HashMap<String, Integer>) hashMap.clone(); 
            int j = i, c = count; 
              
            while(j<i+length){ 
                String word = s.substring(j, j+size); 
              
                if(!hashMap.containsKey(word) || tempMap.get(word) == 0){ 
                    break; 
                }  
                  
                else{ 
                    tempMap.put(word, tempMap.get(word) - 1); 
                    c--; 
                } 
                j += size; 
            } 
              
            if(c == 0){ 
                res.add(i); 
            } 
  
        } 
        return res; 
    } 
  
    public static void main(String[] args){ 
        String s = "capcodthecodcap"; 
        ArrayList<String> L = new ArrayList<>(Arrays.asList("cap", "cod")); 
        ArrayList<Integer> indices = Substring(s, L); 
        for(Integer i : indices){
            System.out.print(i+" "); 
        } 
    }
}
0 9

Time Complexity: O(n-k)*k    (n is the length of string, k is total length after all the list words are concatenated)

References

Translate »