[Solved] Substring with Concatenation of All Words -30 C++,Java,Python – Microsoft,Google ,Amazon,Media.net

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 in s that is equal to the concatenation of any permutation of words. We return an empty array.

Constraints:

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

Solution

class Solution {
public:
	struct matcher {
		struct info { int mtindex, count; };
		unordered_map<string_view, info>dict;
		int different_word_count;

		vector<int>slot;
		int maching_slot_count;

		matcher(const vector<string>& words) {
			int mtind = 0;
			for (auto& word : words) {
				auto find = dict.find(word);
				if (find != dict.end()) {
					++find->second.count;
				}
				else { dict[word] = { mtind++,1 }; }
			}
			different_word_count = mtind;
			slot = vector<int>(different_word_count, 0);
			maching_slot_count = 0;
		}

		void reset() {
			for (auto& i : slot) { i = 0; }
			maching_slot_count = 0;
		}
		bool match() {
			return maching_slot_count == different_word_count;
		}
		void push(string_view sv) {
			auto find = dict.find(sv);
			if (find == dict.end())return;
			if (++slot[find->second.mtindex] == find->second.count) {
				++maching_slot_count;
			}
		}
		void pop(string_view sv) {
			auto find = dict.find(sv);
			if (find == dict.end())return;
			if (--slot[find->second.mtindex] == find->second.count - 1) {
				--maching_slot_count;
			}
		}
	};
	vector<int> findSubstring(string s, const vector<string>& words) {
		int word_count = words.size();
		int word_len = words[0].size();

		matcher matcher(words);

		const char* str = s.c_str();
		int len = s.size();
		vector<int> ret;

		for (int off = 0; off < word_len; off++) {
			const char* beg = str + off, * end = str + len;
			if (beg + word_len * word_count <= end) {
				matcher.reset();
				for (int i = 0; i < word_count; i++) {
					string_view sv(beg + i * word_len, word_len);
					matcher.push(sv);
				}
				if (matcher.match()) {
					ret.push_back(beg - str);
				}
				const char* pos = beg + word_len * word_count;
				while (pos + word_len <= end) {
					string_view del(beg, word_len);
					string_view add(pos, word_len);
					beg += word_len;
					pos += word_len;
					matcher.pop(del);
					matcher.push(add);
					if (matcher.match()) {
						ret.push_back(beg - str);
					}
				}
			}
		}
		return ret;
	}
};

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        int wordLength = words[0].length();
        int totalWordsLength = wordLength * words.length;
        Map<String, Integer> hash = new HashMap<>();
        List<Integer> ans = new ArrayList<>();
        char[] s2 = s.toCharArray();
        for (String value : words) {
            hash.putIfAbsent(value, hash.size());
        }
        int[] count = new int[hash.size()];
        for (String word : words) {
            count[hash.get(word)]++;
        }
        for (int i = 0; i < wordLength; i++) {
            for (int j = i; j <= s.length() - totalWordsLength; j += wordLength) {
                int[] localCount = new int[hash.size()];
                for (int k = j + totalWordsLength - wordLength; k >= j; k -= wordLength) {
                    String str = new String(s2, k, wordLength);     // [ k, k+wordLength )
                    Integer key = hash.get(str);
                    if (!(key != null && count[key] >= ++localCount[key])) {
                        j = k;
                        break;
                    }
                    if (j == k) {
                        ans.add(j);
                    }
                }
            }
        }
        return ans;
    }
}

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        n_word = len(words)
        n_char = len(words[0])
        word2freq = {}
        for word in words:
            if word in word2freq:
                word2freq[word] += 1
            else:
                word2freq[word] = 1

        all_start_ind = []
        for start_ind in range(n_char):
            curr_map = {}
            curr_total = 0
            excessive = False
            for i in range(start_ind, len(s), n_char):
                word = s[i:i+n_char]
                if word in word2freq: # a valid word for permutation 
                    curr_total += 1
                    if word in curr_map: # found valid word
                        curr_map[word] += 1
                        if curr_map[word] > word2freq[word]: 
                            excessive = word
                    else:
                        curr_map[word] = 1

                    earliest_ind = i - (curr_total-1)*n_char
                    while excessive:
                        earliest_word = s[earliest_ind: earliest_ind+n_char]
                        curr_map[earliest_word] -= 1
                        curr_total -= 1
                        if earliest_word == excessive:
                            excessive = False
                            break
                        earliest_ind += n_char
                    if curr_total == n_word:
                        earliest_ind = i - (n_word-1)*n_char

                        all_start_ind.append(earliest_ind)

                        earliest_word = s[earliest_ind: earliest_ind+n_char]
                        curr_total -= 1
                        curr_map[earliest_word] -= 1
                else:
                    curr_total = 0
                    curr_map = {}
        return all_start_ind
    
    def check_map_equal(self, curr_map, ref_map) -> bool:
        for word, freq in curr_map.items():
            if word not in ref_map or freq != ref_map[word]:
                return False
        return True

Happy Learning – If you require any further information, feel free to contact me.