[LeetCode] Substring with Concatenation of All Words

Problem Statement (link):

You are given a string, S, and a list of words, L, that are all of the same length. Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without any intervening characters.
For example, given:
S: "barfoothefoobarman"
L: ["foo", "bar"]
You should return the indices: [0,9].
(order does not matter).

Analysis:
The first solution I tried is to build a hash map that has all the combinations of words, so that we could have O(n/k) processing time afterwards, where n is the length of string S, and k is the length of a concatenated string. But I got MLE...

The second algorithm - see Sol 2 - , which is straightforward, got me an AC. Basically, we traverse the entire string S and check one word (NOT the concatenated long string!) at a time:
- if it matches our hash map, we check next word and so on;
- otherwise, we break immediately to check the word starts at next index

In the worst situation, where every time we check till the last word, we have O(n*m) time complexity, where n is the length of string S and m is the number of words in L.

Code:
Sol 1 - Memory Limit Exceed

class Solution {
public:
    vector<int> findSubstring(string S, vector<string> &L) {
        unordered_set<string> comb; // store all combinations of L
        vector<int> res;
        string src="";
        for (int i=0; i<L.size(); i++) {
            src+=L[i];
        }

        // build up all permutations
        int match_len=L.size()*L[0].size();
        permute(comb, src, 0, match_len);

        // scan S
        for (int i=0; i<S.length(); i++) {
            if (i+match_len<S.length()) {
                string match_str=S.substr(i, match_len);
                if (comb.find(match_str)!=comb.end())
                    res.push_back(i);
            }
        }
        return res;
    }

    void permute(unordered_set<string> &comb, string &src, int st, int len) {
        if (st>=len-1) {
            comb.emplace(src);
            return;
        }
        for (int i=st; i<len; i+=3) {
            swap_words(src, st, i);
            permute(comb, src, st+3, len);
            swap_words(src, st, i);
        }
    }

    void swap_words(string &src, int a, int b) {
        string tmp_a=src.substr(a,3);
        string tmp_b=src.substr(b,3);
        for (int i=a; i<a+3; i++)
            src[i]=tmp_b[i-a];
        for (int i=b; i<b+3; i++)
            src[i]=tmp_a[i-b];
    }
};

Sol 2 - AC

class Solution {
public:
    vector<int> findSubstring(string S, vector<string> &L) {
        vector<int> res;
        unordered_map<string,int> map;
        for (int i=0; i<L.size(); i++)
            map[L[i]]++;

        // scan S
        int len=L[0].size();
        int match_len=L.size()*len;
        if (S.size()<match_len)
            return res;
        for (int i=0; i<=S.size()-match_len; i++) {
            unordered_map<string, int> map2;
            int j=0;
            for (j=0; j<match_len; j+=len) {
                string sub=S.substr(i+j, len);
                if (map.find(sub)!=map.end()) {
                    map2[sub]++;
                    if (map2[sub]>map[sub])
                        break;
                }
                else // immediately end loop
                    break;
            }
            // check if two map are the same
            if (j==match_len) res.push_back(i);
        }
        return res;
    }
};