Challenge description

https://leetcode.com/problems/substring-with-concatenation-of-all-words/

You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.

Example 1:

Input:
  s = "barfoothefoobarman",
  words = ["foo","bar"]
Output: [0,9]

Explanation: Substrings starting at index 0 and 9 are “barfoo” and “foobar” respectively. The output order does not matter, returning [9,0] is fine too.

Example 2:

Input:
  s = "wordgoodgoodgoodbestword",
  words = ["word","good","best","word"]
Output: []

Solution

There are two limitations we need to notice.

• All the words are in the same length

• For the concatenation of words, the order of these words is not important, but each of the words can be used exactly once.

  First, we need to find an approach to check whether a substrings(s) meet these two limitations. The naive solution is iterating all the enumerations of concatenation, but this will perform badly.

  Instead we check the counts of words in a substring. Suppose a corner case:

  s = "aaa" words = ["a"] Output = [0]

  The word’s count map is: “a” => 3, so “aaa” is a valid concatenation.

  The time complexity: $O(NKlog(L))$, where N is the length of s and K is the length of words, L is the length of each words.

  #include <vector> #include <map> #include <string> #include <algorithm> using namespace std; class Solution { public: vector<int> findSubstring(string s, vector<string> &words) { map<string, int> count_map; map<string, int> count; vector<int> ans; // build the count_map for(size_t i=0; i < words.size(); i++) { count_map[words[i]]++; } int size = s.size(); int len = words.size(); if(len == 0) return ans; int str_len = words[0].size(); int k; for(int i = 0; i <= size - len * str_len; i++) { count.clear(); for(k = 0; k < words.size(); k++) { string substr = s.substr(i + k*str_len, str_len); // check whether substr is a valid concatenation if(count_map.find(substr) != count_map.end()) { count[substr]++; if(count[substr] > count_map[substr]) break; } else { break; } } if(k == words.size()) { ans.push_back(i); } } return ans; } };

Preparing for an interview? Check out this!