<p>You are given a string <code>s</code> and an array of strings <code>words</code>. All the strings of <code>words</code> are of <strong>the same length</strong>.</p>

<p>A <strong>concatenated string</strong> is a string that exactly contains all the strings of any permutation of <code>words</code> concatenated.</p>

<ul>
	<li>For example, if <code>words = [&quot;ab&quot;,&quot;cd&quot;,&quot;ef&quot;]</code>, then <code>&quot;abcdef&quot;</code>, <code>&quot;abefcd&quot;</code>, <code>&quot;cdabef&quot;</code>, <code>&quot;cdefab&quot;</code>, <code>&quot;efabcd&quot;</code>, and <code>&quot;efcdab&quot;</code> are all concatenated strings. <code>&quot;acdbef&quot;</code> is not a concatenated string because it is not the concatenation of any permutation of <code>words</code>.</li>
</ul>

<p>Return an array of <em>the starting indices</em> of all the concatenated substrings in <code>s</code>. You can return the answer in <strong>any order</strong>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">s = &quot;barfoothefoobarman&quot;, words = [&quot;foo&quot;,&quot;bar&quot;]</span></p>

<p><strong>Output:</strong> <span class="example-io">[0,9]</span></p>

<p><strong>Explanation:</strong></p>

<p>The substring starting at 0 is <code>&quot;barfoo&quot;</code>. It is the concatenation of <code>[&quot;bar&quot;,&quot;foo&quot;]</code> which is a permutation of <code>words</code>.<br />
The substring starting at 9 is <code>&quot;foobar&quot;</code>. It is the concatenation of <code>[&quot;foo&quot;,&quot;bar&quot;]</code> which is a permutation of <code>words</code>.</p>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">s = &quot;wordgoodgoodgoodbestword&quot;, words = [&quot;word&quot;,&quot;good&quot;,&quot;best&quot;,&quot;word&quot;]</span></p>

<p><strong>Output:</strong> <span class="example-io">[]</span></p>

<p><strong>Explanation:</strong></p>

<p>There is no concatenated substring.</p>
</div>

<p><strong class="example">Example 3:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">s = &quot;barfoofoobarthefoobarman&quot;, words = [&quot;bar&quot;,&quot;foo&quot;,&quot;the&quot;]</span></p>

<p><strong>Output:</strong> <span class="example-io">[6,9,12]</span></p>

<p><strong>Explanation:</strong></p>

<p>The substring starting at 6 is <code>&quot;foobarthe&quot;</code>. It is the concatenation of <code>[&quot;foo&quot;,&quot;bar&quot;,&quot;the&quot;]</code>.<br />
The substring starting at 9 is <code>&quot;barthefoo&quot;</code>. It is the concatenation of <code>[&quot;bar&quot;,&quot;the&quot;,&quot;foo&quot;]</code>.<br />
The substring starting at 12 is <code>&quot;thefoobar&quot;</code>. It is the concatenation of <code>[&quot;the&quot;,&quot;foo&quot;,&quot;bar&quot;]</code>.</p>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 10<sup>4</sup></code></li>
	<li><code>1 &lt;= words.length &lt;= 5000</code></li>
	<li><code>1 &lt;= words[i].length &lt;= 30</code></li>
	<li><code>s</code> and <code>words[i]</code> consist of lowercase English letters.</li>
</ul>

#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;





class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        if(s.length() == 1){
            if(words.size() == 1 && words[0].length() == 1 && words[0] == s) return {0};
            return {};
        }
        int n = 0;
        vector<int> results;
        unordered_map<string,int> string_to_int;
        unordered_map<string,int> string_to_int2;
        unordered_map<string,int> newKeys2;
        vector<string> keys;
        for(string str: words){
            string_to_int[str]++;
            string_to_int2[str]++;
            if(string_to_int[str] == 1) keys.push_back(str);
        }     
     
     function<void(size_t, int, int, unordered_map<string,int>)> boot_Leg_Cache;
        boot_Leg_Cache = [&boot_Leg_Cache,&results, &keys,&string_to_int2, &s, &words, &n](size_t position_of_occurance, int size, int org,unordered_map<string,int> newKeys){
            if(position_of_occurance >= s.length()){
                n = position_of_occurance;
                return;
            } 
            string first = s.substr(org, words[0].length());
            string last = s.substr(position_of_occurance, words[0].length());
            newKeys[last]--;
            size--;
            if(string_to_int2[last] == 0){
                n = position_of_occurance;
                return;
            }

            if(size > 0){
                boot_Leg_Cache(position_of_occurance + words[0].length(), size, org, newKeys);
                return;
            }
            int sum = -1;
            if(size <= 0){
                sum = 0;
                for(string key : keys){
                    if(newKeys[key] != 0){
                        sum = -1;
                        break;
                    }
                }
            }
            newKeys[first]++;

            if(sum == 0){
                results.push_back(org);
                boot_Leg_Cache(position_of_occurance + words[0].length(), 1, org + words[0].length(), newKeys);
            }  
            else if(string_to_int2[last] != 0){
                boot_Leg_Cache(position_of_occurance + words[0].length(), 1, org + words[0].length(), newKeys);
            }
        };

        int size = (words[0].length()) * words.size();
        if(size > s.length()) return {};

        for(int i = 0; i < words[0].length(); ++i){
            n = i;
            while(n <= s.size() - size){
                cout << "n is " << n << endl;
                string str = s.substr(n, words[0].length());
                if(string_to_int[str] != 0){
                    cout << "str is " << str << endl;
                    cout << "is TRUE"  << endl;
                    if(words.size() == 1){
                        results.push_back(n);
                    }
                    else{
                        string_to_int[str]--;
                        boot_Leg_Cache(n + words[0].length(), words.size() - 1, n, string_to_int);
                        string_to_int[str]++;
                    }
                }
                n+= words[0].length();
            }
        }

        sort(results.begin(), results.end());
        
        return results;
    }
};
251037