Problem statement

https://leetcode.com/problems/count-pairs-of-equal-substrings-with-minimum-difference/

Solution

The idea is that we only interested in substrings of length 1. Indeed, if we have length 2 or more, we can remove last letters and decrease j-a.

So, all we need to do is to consider for each symbol first occurence in s1 and last occurence in s2 and choose minimum difference.

Complexity

Time complexity is O(n + m), where n and m are sizes of strings and space complexity is O(s), where s is size of alphabet.

Code

class Solution:
    def countQuadruples(self, s1, s2):
        n1, n2 = len(s1), len(s2)
        d1, d2 = Counter(), Counter()
        for i in range(n1 - 1, -1, -1):
            d1[s1[i]] = i
        for j in range(n2): 
            d2[s2[j]] = j
            
        diffs = [d2[el] - d1[el] for el in d1 if el in d2]
        if not diffs: return 0
        return diffs.count(max(diffs))