You are given two $0$ indexed strings, firstString and secondString, each consisting of lowercase English letters.

You need to find the number of index quadruples $(i, j, a, b)$ that satisfy the following conditions:

• $0 \leq i \leq j <$ firstString.length

• $0 \leq a \leq b <$ secondString.length

• The substring of firstString from index $i$ to $j$ is identical to the substring of secondString from index $a$ to $b$

• The value of $j - a$ is minimized among all valid quadruples

Return the number of quadruples that achieve this minimum value of $j - a$.

Constraints:

• $1 \leq$ firstString.length, secondString.length $\leq 2 imes 10^5$

• Both firstString and secondString consist only of lowercase English letters.

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.