You are viewing a single comment's thread. Return to all comments →
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
Seems like cookies are disabled on this browser, please enable them to open this website
Substring Diff
You are viewing a single comment's thread. Return to all comments →
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.