aboutsummaryrefslogtreecommitdiff
path: root/substring_concentration.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'substring_concentration.cpp')
-rw-r--r--substring_concentration.cpp37
1 files changed, 37 insertions, 0 deletions
diff --git a/substring_concentration.cpp b/substring_concentration.cpp
new file mode 100644
index 0000000..b989375
--- /dev/null
+++ b/substring_concentration.cpp
@@ -0,0 +1,37 @@
+#include "leetcode.h"
+
+class Solution {
+public:
+ vector<int> findSubstring(string s, vector<string> &words) {
+ int len = words[0].size(), n = words.size(), sSize = s.size(), left, found;
+ vector<int> result;
+ unordered_map<string, int> freq, temp;
+ for (auto word : words)
+ freq[word]++;
+ for (int i = 0; i < len; i++) {
+ temp.clear();
+ left = i, found = 0;
+ for (int j = i; j <= sSize - len; j += len) {
+ string curr = s.substr(j, len);
+ if (freq.find(curr) != freq.end()) {
+ temp[curr]++;
+ found++;
+ while (freq[curr] < temp[curr]) {
+ temp[s.substr(left, len)]--;
+ found--;
+ left += len;
+ }
+ if (found == n)
+ result.push_back(left);
+ } else {
+ temp.clear();
+ found = 0;
+ left = j + len;
+ }
+ }
+ }
+ return result;
+ }
+};
+
+int main() {}