• + 1 comment

    Didnt see a good python solution for this problem. Mine is O(n * m) solution (n,m are lens of s1 and s2).

    It basically looks at diagonals how @bluephirus described it.

    def substringDiff(k, s1, s2):
        # Write your code here
        
        def matches(str1, str2):
            maxLen = 0
            lengthS1 = len(str1)
            lengthS2 = len(str1)
            for idx in range(lengthS1):
                j = 0
                queue = deque()
                res = [0] * 2
                trackLen = 0
                for i in range(idx, lengthS1):
                    if j > lengthS2: # ensure doesnt exceed
                        break
                        
                    if str1[i] == str2[j]:
                        res[1] += 1
                        queue.append(1)
                        trackLen += 1
                    else: 
                        res[0] += 1
                        queue.append(0)
                        trackLen += 1
                    while res[0] > k:
                        val = queue.popleft()
                        res[val] -= 1
                        trackLen -= 1
                    if trackLen > maxLen:
                        maxLen = trackLen
                    j += 1
            return maxLen
    
        return max(matches(s1, s2), matches(s2, s1))
    # n 0 0 0 0 0 0
    # o 0 0 0 0 0 0