Question

Formatted question description: https://leetcode.ca/all/30.html

You are given a string s and an array of strings words. All the strings of words are of the same length.

A concatenated substring in s is a substring that contains all the strings of any permutation of words concatenated.

For example, if words = ["ab","cd","ef"], then "abcdef", "abefcd", "cdabef", "cdefab", "efabcd", and "efcdab" are all concatenated strings. "acdbef" is not a concatenated substring because it is not the concatenation of any permutation of words.

Return the starting indices of all the concatenated substrings in s. You can return the answer in any order.

Example 1:

Input: s = "barfoothefoobarman", words = ["foo","bar"]
Output: [0,9]
Explanation: Since words.length == 2 and words[i].length == 3, the concatenated substring has to be of length 6.
The substring starting at 0 is "barfoo". It is the concatenation of ["bar","foo"] which is a permutation of words.
The substring starting at 9 is "foobar". It is the concatenation of ["foo","bar"] which is a permutation of words.
The output order does not matter. Returning [9,0] is fine too.

Example 2:

Input: s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
Output: []
Explanation: Since words.length == 4 and words[i].length == 4, the concatenated substring has to be of length 16.
There is no substring of length 16 is s that is equal to the concatenation of any permutation of words.
We return an empty array.

Example 3:

Input: s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
Output: [6,9,12]
Explanation: Since words.length == 3 and words[i].length == 3, the concatenated substring has to be of length 9.
The substring starting at 6 is "foobarthe". It is the concatenation of ["foo","bar","the"] which is a permutation of words.
The substring starting at 9 is "barthefoo". It is the concatenation of ["bar","the","foo"] which is a permutation of words.
The substring starting at 12 is "thefoobar". It is the concatenation of ["the","foo","bar"] which is a permutation of words.

Constraints:

1 <= s.length <= 10⁴
1 <= words.length <= 5000
1 <= words[i].length <= 30
s and words[i] consist of lowercase English letters.

Algorithm

To determine whether a substring of length len in string s is a word in the array words, we can use a HashMap to map each word to its frequency count. Since the words array may contain duplicates, we must count the number of occurrences of each word.

To check all substrings of length nxlen in s, we traverse through all indices i from 0 to (int)s.size()-nxlen. Note that we must convert the size() of s to an integer before performing the operation to avoid errors.

For each substring of length nxlen, we check if it is composed of all words in words. To do this, we create another HashMap to map each word to its frequency count within the substring. If a word in the substring is not in words, we break out of the loop. Otherwise, we increment the count of the word in the substring’s HashMap. If the count of the word in the substring’s HashMap exceeds the count of the word in the words HashMap, we break out of the loop. If j is exactly equal to the number of words in words, we add the current index i to the result.

Code

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class Substring_with_Concatenation_of_All_Words {

	public static void main(String[] args) {
		HashMap<String, Boolean> hm = new HashMap<String, Boolean>();
		hm.put("a", true);

		// @note: ugly type convert...
		HashMap<String, Boolean> copy = (HashMap<String, Boolean>) hm.clone();
		copy.put("a", false);

		System.out.println(hm.entrySet());
		System.out.println(copy.entrySet());
	}

	public class Solution {

	    List<Integer> list = new ArrayList<Integer>();

        // pre-process a hashmap storing all short words, for quick look up
	    HashMap<String, Integer> hm = new HashMap<String, Integer>(); // L words to count

	    public List<Integer> findSubstring(String s, String[] words) {

	        if (s.length() == 0 || s == null || words.length == 0 || words == null || s.length() < words.length * words[0].length())
	            return list;

	        int eachlen = words[0].length();
	        int totalLength = words.length * words[0].length();

	        // pre-process hashmap
	        for (String e: words) {
	            if (hm.containsKey(e)) {
	                hm.put(e, hm.get(e) + 1);
	            } else {
	                hm.put(e, 1);
	            }
	        }

	        // go through s to find match
	        for (int i = 0; i <= s.length() - totalLength; i++) {

	            String sub = s.substring(i, i + totalLength);
	            if (isValid(sub, eachlen))
	                list.add(i);

	        }

	        return list;
	    }


	    public boolean isValid(String s, int eachlen) {
	        HashMap<String, Integer> hmcopy = new HashMap<String, Integer>(hm);

	        // increment i by eachlen
	        for (int i = 0; i <= s.length() - eachlen; i = i + eachlen) {

	            String current = s.substring(i, i + eachlen);

	            // if its count==0 then false, eg:foofoo
	            if (hmcopy.containsKey(current) && hmcopy.get(current) > 0) {
	                // if hm has it, then decrease its count
	                hmcopy.put(current, hmcopy.get(current) - 1);
	            } else {
	                return false;
	            }
	        }

	        return true;
	    }
	}

}

############

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

// OJ: https://leetcode.com/problems/substring-with-concatenation-of-all-words/
// Time: O(MNL)
// Space: O(ML)
class Solution {
private:
public:
    vector<int> findSubstring(string s, vector<string>& A) {
        if (A.empty()) return {};
        int L = A.size(), M = A[0].size(), last = s.size() - M * L;
        unordered_map<string, int> cnt;
        for (auto &w : A) ++cnt[w];
        vector<int> ans;
        function<bool(int, int)> dfs = [&](int i, int seen) {
            if (seen == L) return true;
            int &c = cnt[s.substr(i, M)];
            if (!c) return false;
            c--;
            bool ans = dfs(i + M, seen + 1);
            c++;
            return ans;
        };
        for (int i = 0; i <= last; ++i) {
            if (dfs(i, 0)) ans.push_back(i);
        }
        return ans;
    }
};

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        cnt = Counter(words)
        sublen = len(words[0])
        n, m = len(s), len(words)
        ans = []
        for i in range(sublen):
            cnt1 = Counter()
            l = r = i
            t = 0
            while r + sublen <= n:
                w = s[r : r + sublen]
                r += sublen
                if w not in cnt:
                    l = r
                    cnt1.clear()
                    t = 0
                    continue
                cnt1[w] += 1
                t += 1
                while cnt1[w] > cnt[w]:
                    remove = s[l : l + sublen]
                    l += sublen
                    cnt1[remove] -= 1
                    t -= 1
                if m == t:
                    ans.append(l)
        return ans

############

from collections import deque


class Solution(object):
  def findSubstring(self, s, words):
    """
    :type s: str
    :type words: List[str]
    :rtype: List[int]
    """
    if len(words) > len(s):
      return []
    d = {}
    t = {}
    ans = []
    deq = deque([])
    wl = len(words[0])
    fullscore = 0
    for word in words:
      d[word] = d.get(word, 0) + 1
      fullscore += 1

    for i in range(0, len(s)):
      head = start = i
      t.clear()
      score = 0

      while start + wl <= len(s) and s[start:start + wl] in d:
        cword = s[start:start + wl]
        t[cword] = t.get(cword, 0) + 1
        if t[cword] <= d[cword]:
          score += 1
        else:
          break
        start += wl

      if score == fullscore:
        ans.append(head)

    return ans

func findSubstring(s string, words []string) []int {
	cnt := map[string]int{}
	for _, w := range words {
		cnt[w]++
	}
	subLen := len(words[0])
	n, m := len(s), len(words)
	var ans []int
	for i := 0; i < subLen; i++ {
		cnt1 := map[string]int{}
		l, r := i, i
		t := 0
		for r+subLen <= n {
			w := s[r : r+subLen]
			r += subLen
			if _, ok := cnt[w]; !ok {
				l = r
				t = 0
				cnt1 = map[string]int{}
				continue
			}
			cnt1[w]++
			t++
			for cnt1[w] > cnt[w] {
				remove := s[l : l+subLen]
				l += subLen
				cnt1[remove]--
				t--
			}
			if t == m {
				ans = append(ans, l)
			}
		}
	}
	return ans
}

public class Solution {
    public IList<int> FindSubstring(string s, string[] words) {
        var wordsDict = new Dictionary<string, int>();
        foreach (var word in words)
        {
            if (!wordsDict.ContainsKey(word))
            {
                wordsDict.Add(word, 1);
            }
            else
            {
                ++wordsDict[word];
            }
        }
        
        var wordOfS = new string[s.Length];
        var wordLength = words[0].Length;
        var wordCount = words.Length;
        for (var i = 0; i <= s.Length - wordLength; ++i)
        {
            var substring = s.Substring(i, wordLength);
            if (wordsDict.ContainsKey(substring))
            {
                wordOfS[i] = substring;
            }
        }
        
        var result = new List<int>();
        for (var i = 0; i <= s.Length - wordLength * wordCount; ++i)
        {
            var tempDict = new Dictionary<string, int>(wordsDict);
            var tempCount = 0;
            for (var j = i; j <= i + wordLength * (wordCount - 1); j += wordLength)
            {
                if (wordOfS[j] != null && tempDict[wordOfS[j]] > 0)
                {
                    --tempDict[wordOfS[j]];
                    ++tempCount;
                }
                else
                {
                    break;
                }
            }
            if (tempCount == wordCount)
            {
                result.Add(i);
            }
        }
        
        return result;
    }
}

function findSubstring(s: string, words: string[]): number[] {
    const cnt: Map<string, number> = new Map();
    for (const w of words) {
        cnt.set(w, (cnt.get(w) || 0) + 1);
    }
    const m = s.length;
    const n = words.length;
    const k = words[0].length;
    const ans: number[] = [];
    for (let i = 0; i < k; ++i) {
        const cnt1: Map<string, number> = new Map();
        let l = i;
        let r = i;
        let t = 0;
        while (r + k <= m) {
            const w = s.slice(r, r + k);
            r += k;
            if (!cnt.has(w)) {
                cnt1.clear();
                l = r;
                t = 0;
                continue;
            }
            cnt1.set(w, (cnt1.get(w) || 0) + 1);
            ++t;
            while (cnt1.get(w)! - cnt.get(w)! > 0) {
                const remove = s.slice(l, l + k);
                cnt1.set(remove, cnt1.get(remove)! - 1);
                l += k;
                --t;
            }
            if (t === n) {
                ans.push(l);
            }
        }
    }
    return ans;
}

30 - Substring with Concatenation of All Words

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions