30. Substring with Concatenation of All Words

/**
Refer: https://leetcode.com/problems/substring-with-concatenation-of-all-words/discuss/13656/An-O(N)-solution-with-detailed-explanation

Time Complexity = O(length of the string * length of one word)
Spcae Complexity = O(words.length)
*/
class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> result = new ArrayList<>();
        if (s == null || words == null || words.length == 0 || s.length() < words.length * words[0].length()) {
            return result;
        }

        HashMap<String, Integer> countMap = new HashMap<>();
        for (String word : words) {
            countMap.put(word, countMap.getOrDefault(word, 0) + 1);
        }
        int n = s.length();
        int numOfWords = words.length;
        int sizeOfWord = words[0].length();

        for (int i = 0; i < sizeOfWord; i++) {
            int count = 0;
            int low = i;
            HashMap<String, Integer> seenMap = new HashMap<>();
            for (int j = i; j <= n-sizeOfWord; j += sizeOfWord) {
                String str = s.substring(j, j+sizeOfWord);
                if (!countMap.containsKey(str)) {
                    seenMap = new HashMap<>();
                    count = 0;
                    low = j+sizeOfWord;
                } else {
                    seenMap.put(str, seenMap.getOrDefault(str, 0) + 1);
                    count++;
                    while (seenMap.get(str) > countMap.get(str)) {
                        String toBeRemoved = s.substring(low, low+sizeOfWord);
                        seenMap.put(toBeRemoved, seenMap.get(toBeRemoved) - 1);
                        count--;
                        low += sizeOfWord;
                    }
                    if (count == numOfWords) {
                        result.add(low);
                    }
                }
            }
        }
        return result;
    }
}

/**
Refer : https://leetcode.com/problems/substring-with-concatenation-of-all-words/discuss/13658/Easy-Two-Map-Solution-(C++Java)

Time Complexity: O(lengthOfString * numOfWords)
Space Complexity: O(numOfWords)
*/
class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> result = new ArrayList<>();
        if (s == null || words == null || words.length == 0 || s.length() < words.length * words[0].length()) {
            return result;
        }

        HashMap<String, Integer> countMap = new HashMap<>();
        for (String word : words) {
            countMap.put(word, countMap.getOrDefault(word, 0) + 1);
        }
        int n = s.length();
        int numOfWords = words.length;
        int sizeOfWord = words[0].length();

        for (int i = 0; i < (n - numOfWords * sizeOfWord + 1); i++) {
            HashMap<String, Integer> seenMap = new HashMap<>();
            int count = 0;
            for (int j = i; j < i + numOfWords * sizeOfWord; j += sizeOfWord) {
                String word = s.substring(j, j+sizeOfWord);
                if (!countMap.containsKey(word)) {
                    break;
                }
                seenMap.put(word, seenMap.getOrDefault(word, 0) + 1);
                if (seenMap.get(word) > countMap.get(word)) {
                    break;
                }
                count++;
            }
            if (count == numOfWords) {
                result.add(i);
            }
        }
        return result;
    }
}