# LeetCode 1794. Count Pairs of Equal Substrings With Minimum Difference



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).
* `j - a` is the **minimum** possible value among all quadruples that satisfy the previous conditions.

Return _the **number** of such quadruples_.

**Example 1:**

```
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.
```

**Example 2:**

```
Input: firstString = "ab", secondString = "cd"
Output: 0
Explanation: There are no quadruples satisfying all the conditions.
```

**Constraints:**

* `1 <= firstString.length, secondString.length <= 2 * 10^5`
* Both strings consist only of lowercase English letters.

## Solution

[English Version in Youtube](https://youtu.be/1fnPLW5Tbxc)

[中文版解答Youtube Link](https://youtu.be/oXm_wtSecxs)

[中文版解答Bilibili Link](https://www.bilibili.com/video/BV12B4y1A7e1/)

```
class Solution {
public:
    int countQuadruples(string firstString, string secondString) {
        unordered_map<char, int> last_occurence;
        for (int i = 0; i < secondString.length(); i++) {
            last_occurence[secondString[i]] = i;
        }
        
        int minimum_j_minus_a = INT_MAX;
        int cnt = 0;
        for (int i = 0; i < firstString.length(); i++) {
            char ch = firstString[i];
            if (last_occurence.count(ch) > 0) {
                int j_minus_a = i - last_occurence[ch];
                if (j_minus_a < minimum_j_minus_a) {
                    minimum_j_minus_a = j_minus_a;
                    cnt = 1;
                } else if (j_minus_a == minimum_j_minus_a) {
                    cnt++;
                }
            }
        }
        
        return cnt;
    }
};
```
