Count Pairs of Equal Substrings With Minimum Difference — LeetCode 1794 Python Solution

The problem

You are given two strings firstString and secondString that are 0-indexed and consist only of lowercase English letters. Count the number of index quadruples (i,j,a,b) that satisfy the following conditions: 0 <= i <= j < firstString.length 0 <= a <= b < secondString.length The substring of firstString that starts at the ith character and ends at the jth character (inclusive) is equal to the substring of secondString that starts at the ath character and ends at the bth character (inclusive).

Example

Input

firstString = "abcd", secondString = "bccda"

Output

1

Explanation

The quadruple (0,0,4,4) is the only one that satisfies all the conditions and minimizes j - a.

Python solution

class Solution:
    def countQuadruples(self, firstString: str, secondString: str) -> int:
        last = {c: i for i, c in enumerate(secondString)}
        ans, mi = 0, inf
        for i, c in enumerate(firstString):
            if c in last:
                t = i - last[c]
                if mi > t:
                    mi = t
                    ans = 1
                elif mi == t:
                    ans += 1
        return ans

Complexity

Pattern: Greedy

Take the locally best option every time — when you can prove that never costs you later. LeetCode 1794. Count Pairs of Equal Substrings With Minimum Difference is filed here because LeetCode tags it Greedy, which is the vocabulary this hub collects.

The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.

Related problems