substring-with-concatenation-of-all-words

malipramod · malipramod · commit 125bdffb2fb1 · 2019-07-24T18:11:25.000+05:30
diff --git a/hard/0029 substring-with-concatenation-of-all-words/readme.md b/hard/0029 substring-with-concatenation-of-all-words/readme.md
@@ -0,0 +1,28 @@
+# 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 "barfoor" 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: []
+
+## More info
+
+<https://leetcode.com/problems/substring-with-concatenation-of-all-words/>
diff --git a/hard/0029 substring-with-concatenation-of-all-words/substring-with-concatenation-of-all-words.js b/hard/0029 substring-with-concatenation-of-all-words/substring-with-concatenation-of-all-words.js
@@ -0,0 +1,26 @@
+/**
+ * @param {string} s
+ * @param {string[]} words
+ * @return {number[]}
+ */
+var findSubstring = function (s, words) {
+    if (!words || words.length === 0) return [];
+    
+    let uniqueWordsMap = {};
+    let n = words.length, m = words[0].length;
+    let len = n * m;
+    let resp = [];
+    for (word of words) uniqueWordsMap[word] = ~~uniqueWordsMap[word] + 1;
+    for (let i = 0; i < s.length - len + 1; i++) {
+        let temp = Object.assign({}, uniqueWordsMap);
+        for (let j = i; j < i + len; j += m) {
+            const str = s.substr(j, m);
+            if (!(str in temp)) break;
+            if (--temp[str] === 0) delete temp[str];
+        }
+        if (Object.keys(temp).length === 0) resp.push(i);
+    }
+    return resp;
+};
+
+console.log(findSubstring("", []))
