[LeetCode] 30. Substring with Concatenation of All Words

Problem : https://leetcode.com/problems/substring-with-concatenation-of-all-words/

Because all the words are with same length.  Assume word length is N, the code pickup every substring of length N to check if the substring is in the words array.

Time Complexity : O ( Len(s) *  Len(words) )

Space Complexity:  O ( N )

from collections import defaultdict

class Solution(object):
    def findSubstring(self, s, words):
        """
        :type s: str
        :type words: List[str]
        :rtype: List[int]
        """
        
        result = []
        
        if not s or not words:
            return result
        
        L = len(words)
        N = len(words[0])
        
        wordCnt = defaultdict(int)
        for w in words:
            wordCnt[w] += 1
            
       
        for i in range(len(s) - N*L + 1):
            # counter of a valid word in range [i : i+N*L+1]
            strCnt = defaultdict(int)
            
            for j in range(L):
                substr = s[i+j*N: i+j*N+N]
                
                if wordCnt[substr] == 0:
                    break
                    
                strCnt[substr] += 1
                
                if strCnt[substr] > wordCnt[substr]:
                    break
            else:
                result.append(i)
                
        return result