Substring With Concatenation of All Words Problem Solution

Substring With Concatenation of All Words Problem: 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 :

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.

Substring With Concatenation of All Words Problem Solution

Problem Solution In Python

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        if(len(words)==0):
            return []
        N = len(words[0])
        if(len(s) < N*len(words)):
            return []
        i=0;location=[]
        def recursion(firstWord,words,s,location,N):
            if not words:
                return location
            if(firstWord in set(words)):
                words.remove(firstWord)
                pos = recursion(s[location+N:location+2*N],words,s,location+N,N)
                if(pos == -1):
                    return -1
                else:
                    return location
            else:
                return -1
        while(i<len(s)):
            firstWord = s[i:i+N]
        
            pos = recursion(firstWord,words[:],s,i,N)
            
            if(pos!=-1):
                location.append(pos)
            i+=1
        return location

Problem Solution In Java

public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> res = new ArrayList<>();
        if(words.length == 0 || words[0].length() == 0 || s.length() == 0) return res;
        int wordLen = words[0].length();
        int wordNum = words.length;
        int windowSize = wordLen * wordNum;
        Map<String,Integer> map = new HashMap<>();
        
        for(String eachWord : words) {
            map.put(eachWord,map.getOrDefault(eachWord,0) + 1);
        }
       
        for(int i = 0;i + windowSize - 1 < s.length();i++) {
            String lastWord = s.substring(i + windowSize - wordLen,i + windowSize);
            if(map.containsKey(lastWord)) {
                boolean bre = false;
                Map<String,Integer> currMap = new HashMap<>(map);
                for(int j = i;j < i + windowSize;j += wordLen) {
                    String currWord = s.substring(j,j + wordLen);
                    currMap.put(currWord,currMap.getOrDefault(currWord,0) - 1);
                    if(currMap.get(currWord) < 0) {
                        bre = true;
                        break;
                    }
                }
                if(!bre)res.add(i);
            }
        }
        return res;
    }

Problem Solution In C++

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int>ans;
        if(!s.size() || !words.size())
            return ans;
        unordered_map<string,int>mp1;
        unordered_map<string,int>mp2;
        for(auto word:words)
        {
            mp1[word]++;
        }
        int len = words.size();
        int tl = words[0].size()*len;
        int sl = words[0].size();
        int i = 0;
        if(tl>s.size())
            return ans;
        while(i<=s.size()-tl)
        {
            
            string sub = s.substr(i,tl);
            int k = 0;
            int n = 0;
            while(k<words.size())
            {
                string temp = sub.substr(n,sl);
                mp2[temp]++;
                n += sl;
                k++;
            }
            if(mp2 == mp1)
                ans.push_back(i);
            mp2.clear();
            i++;
        }
        return ans;
    }
};

Problem Solution In C

typedef struct entry{
    char* word;
    int occurred;
    int occurrence;
    struct entry* next;
    
} dic_entry;

dic_entry* add_entry(dic_entry* dic, char* word)
{
    dic_entry* new_entry = (dic_entry*)malloc(sizeof(dic_entry));
    new_entry->word = (char*)malloc(sizeof(char)*(strlen(word)+1));
    strcpy(new_entry->word, word);
    new_entry->occurred = 0;
    new_entry->occurrence = 1;
    new_entry->next = NULL;
    dic_entry* head = dic;
    
    if(dic == NULL)
    {
        head = new_entry;
    }
    else
    {
        while(dic->next)
        {
            dic = dic->next;
        }
        
        dic->next = new_entry;
    }
    return head;
}

dic_entry* find_entry(dic_entry* dic, char* word, int len)
{
    
    dic_entry* head = dic;
    while(head)
    {
        if(!strncmp(head->word, word, len))
        {
            return head;
        }
        head = head->next;
    }
    return NULL;
}

void reset(dic_entry* dic)
{
    dic_entry* head = dic;
    
    while(head)
    {
        head->occurred = 0;
        head = head->next;
    }
}

void free_dic(dic_entry* dic)
{
    dic_entry* head = dic;
    dic_entry* temp;
    
    while(head)
    {
        free(head->word);
        temp = head;
        head = head->next;
        free(temp);
    }
}


int* findSubstring(char * s, char ** words, int wordsSize, int* returnSize){
    
    int* result = (int*)malloc(sizeof(int));
    int resultCount = 0;
    dic_entry* dic = NULL;
    dic_entry* temp;
    int j;
    int string_len = (int)strlen(s);
    
    if (wordsSize == 0)
    {
        *returnSize = 0;
        return result;
    }
    
    int word_len = strlen(words[0]);
    
    for(int i = 0; i < wordsSize; i++)
    {
        
        temp = find_entry(dic, words[i], word_len);
        
        if(temp != NULL)
        {
            temp->occurrence++;
        }
        else
        {
            dic = add_entry(dic, words[i]);
        }
        
    }
    
    for(int i = 0; i <= string_len - wordsSize*word_len; i++)
    {
        for(j = 0; j < wordsSize; j++)
        {
            temp = find_entry(dic, s+j*word_len+i, word_len);
            if(temp)
            {
                temp->occurred++;
                if (temp->occurred > temp->occurrence)
                    break;
            }
            else
            {
                break;
            }
        }
        
        if(j == wordsSize)
        {
            result[resultCount++] = i;
            result = (int*)realloc(result, sizeof(int)*(resultCount+1));
        }
        
        reset(dic);
    }
    
    
    free_dic(dic);
    *returnSize = resultCount;
    return result;
    
}