Substring with Concatenation of All Words

Problem: Substring with Concatenation of All Words

The solution is quite trivial and dummy. We just try with all potential substrings with possible length and use hash tables to maintain frequencies of words.

Code in Python:

class Solution(object):
    def findSubstring(self, s, words):
        if not s or not words or not words[0]:
            return []
        n, k, t = len(s), len(words[0]), len(words)*len(words[0])
        freq = {}
        for word in words:
            freq[word] = freq[word] + 1 if word in freq else 1
        ans = []
        for i in xrange(min(k, n - t + 1)):
            l = r = i
            curr = {}
            while r + k <= n:
                w = s[r:r+k]
                r += k
                if w not in freq:
                    l = r
                    curr.clear()
                else:
                    curr[w] = curr[w]+1 if w in curr else 1
                    while curr[w] > freq[w]:
                        curr[s[l:l+k]] -= 1
                        l += k
                    if r-l == t:
                        ans.append(l)
        return ans

Code in Java:

public class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        if (s.length() == 0 || words.length == 0 || words[0].length() == 0)
            return new ArrayList<Integer>();

        int n = s.length(), k = words[0].length(), t = words.length*words[0].length();
        HashMap<String, Integer> freq = new HashMap<String, Integer>();

        for (String word : words) {
            if (freq.get(word) != null)
                freq.put(word, freq.get(word)+1);
            else
                freq.put(word, 1);
        }

        List<Integer> res = new ArrayList<Integer>();
        for (int i = 0; i < Math.min(k, n-t+1);i++) {
            int l = i, r = i;
            HashMap<String, Integer> curr = new HashMap<String, Integer>();
            while (r+k <= n) {
                String w = s.substring(r, r+k);
                r += k;
                if (freq.get(w) == null) {
                    l = r;
                    curr.clear();
                } else {
                    if (curr.get(w) != null)
                        curr.put(w, curr.get(w)+1);
                    else
                        curr.put(w, 1);
                    while (curr.get(w) > freq.get(w)) {
                        curr.put(s.substring(l,l+k), curr.get(s.substring(l,l+k))-1);
                        l += k;
                    }
                    if (r-l == t) {
                        res.add(l);
                    }
                }
            }
        }

        return res;
    }
}