30 - Substring with Concatenation of All Words

 JAVA

• class Solution {
      public List<Integer> findSubstring(String s, String[] words) {
          Map<String, Integer> cnt = new HashMap<>();
          for (String w : words) {
              cnt.merge(w, 1, Integer::sum);
          }
          int m = s.length(), n = words.length;
          int k = words[0].length();
          List<Integer> ans = new ArrayList<>();
          for (int i = 0; i < k; ++i) {
              Map<String, Integer> cnt1 = new HashMap<>();
              int l = i, r = i;
              int t = 0;
              while (r + k <= m) {
                  String w = s.substring(r, r + k);
                  r += k;
                  if (!cnt.containsKey(w)) {
                      cnt1.clear();
                      l = r;
                      t = 0;
                      continue;
                  }
                  cnt1.merge(w, 1, Integer::sum);
                  ++t;
                  while (cnt1.get(w) > cnt.get(w)) {
                      String remove = s.substring(l, l + k);
                      l += k;
                      cnt1.merge(remove, -1, Integer::sum);
                      --t;
                  }
                  if (t == n) {
                      ans.add(l);
                  }
              }
          }
          return ans;
      }
  }

C++

• class Solution {
  public:
      vector<int> findSubstring(string s, vector<string>& words) {
          unordered_map<string, int> cnt;
          for (auto& w : words) {
              ++cnt[w];
          }
          int m = s.size(), n = words.size(), k = words[0].size();
          vector<int> ans;
          for (int i = 0; i < k; ++i) {
              unordered_map<string, int> cnt1;
              int l = i, r = i;
              int t = 0;
              while (r + k <= m) {
                  string w = s.substr(r, k);
                  r += k;
                  if (!cnt.count(w)) {
                      cnt1.clear();
                      l = r;
                      t = 0;
                      continue;
                  }
                  ++cnt1[w];
                  ++t;
                  while (cnt1[w] > cnt[w]) {
                      string remove = s.substr(l, k);
                      l += k;
                      --cnt1[remove];
                      --t;
                  }
                  if (t == n) {
                      ans.push_back(l);
                  }
              }
          }
          return ans;
      }
  };