Skip to content

30. Substring with Concatenation of All Words 👍

  • Time: $O(|\texttt{s}||\texttt{words}||\texttt{words[0]}|)$
  • Space: $O(\Sigma |\texttt{words[i]}|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
 public:
  vector<int> findSubstring(string s, vector<string>& words) {
    if (s.empty() || words.empty())
      return {};

    const int k = words.size();
    const int n = words[0].length();
    vector<int> ans;
    unordered_map<string, int> count;

    for (const string& word : words)
      ++count[word];

    for (int i = 0; i < s.length() - k * n + 1; ++i) {
      unordered_map<string, int> seen;
      int j;
      for (j = 0; j < k; ++j) {
        const string& word = s.substr(i + j * n, n);
        if (++seen[word] > count[word])
          break;
      }
      if (j == k)
        ans.push_back(i);
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
  public List<Integer> findSubstring(String s, String[] words) {
    if (s.isEmpty() || words.length == 0)
      return new ArrayList<>();

    final int k = words.length;
    final int n = words[0].length();
    List<Integer> ans = new ArrayList<>();
    Map<String, Integer> count = new HashMap<>();

    for (final String word : words)
      count.merge(word, 1, Integer::sum);

    for (int i = 0; i <= s.length() - k * n; ++i) {
      Map<String, Integer> seen = new HashMap<>();
      int j = 0;
      for (; j < k; ++j) {
        final String word = s.substring(i + j * n, i + j * n + n);
        seen.merge(word, 1, Integer::sum);
        if (seen.get(word) > count.getOrDefault(word, 0))
          break;
      }
      if (j == k)
        ans.add(i);
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
  def findSubstring(self, s: str, words: list[str]) -> list[int]:
    if len(s) == 0 or words == []:
      return []

    k = len(words)
    n = len(words[0])
    ans = []
    count = collections.Counter(words)

    for i in range(len(s) - k * n + 1):
      seen = collections.defaultdict(int)
      j = 0
      while j < k:
        word = s[i + j * n: i + j * n + n]
        seen[word] += 1
        if seen[word] > count[word]:
          break
        j += 1
      if j == k:
        ans.append(i)

    return ans