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.length0 <= a <= b < secondString.lengthfirstString 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 * 105Problem Overview: You are given two strings and need to count pairs of equal substrings (effectively matching characters) such that the absolute difference between their indices is minimized. First determine the smallest possible index difference |i - j| where first[i] == second[j], then count how many pairs achieve that minimum.
Approach 1: Brute Force Character Matching (O(n * m) time, O(1) space)
Check every pair of indices between the two strings. For each i in the first string and j in the second string, compare characters. When they match, compute |i - j|. Track the smallest difference seen so far and the number of pairs that produce it. This approach is straightforward and proves correctness, but the nested iteration makes it too slow for larger inputs.
Approach 2: Greedy + Hash Table with Position Lists (O(n + m) time, O(n + m) space)
Store the indices of each character from the second string in a hash table where the key is the character and the value is a list of positions. Then iterate through the first string. For each character, look up its list of indices in the second string and compare positions using a two‑pointer scan to find the closest indices. Because each pointer only moves forward, the total work across all comparisons stays linear. Each time you compute |i - j|, update the global minimum and maintain the count of pairs achieving that difference.
The key insight is that for a fixed character, the smallest index difference must occur between nearby positions in the two sorted index lists. Scanning them with two pointers avoids checking every combination. The hash table enables constant-time access to the relevant index list for each character.
This technique combines hash table grouping with a greedy pointer movement strategy on sorted indices. The approach works well because characters are processed independently and each index participates in only a few comparisons. It is also cache-friendly and simple to implement across languages.
Recommended for interviews: The Greedy + Hash Table approach. Interviewers expect you to reduce the brute force comparison by grouping indices with a hash table and scanning them efficiently using a greedy pointer strategy. Demonstrating the brute force first shows understanding of the problem, while the optimized linear solution highlights algorithmic maturity with string processing.
The problem actually asks us to find a smallest index i and a largest index j such that firstString[i] equals secondString[j], and the value of i - j is the smallest among all index pairs that meet the conditions.
Therefore, we first use a hash table last to record the index of the last occurrence of each character in secondString. Then we traverse firstString. For each character c, if c has appeared in secondString, we calculate i - last[c]. If the value of i - last[c] is less than the current minimum value, we update the minimum value and set the answer to 1. If the value of i - last[c] equals the current minimum value, we increment the answer by 1.
The time complexity is O(m + n), and the space complexity is O(C). Here, m and n are the lengths of firstString and secondString respectively, and C is the size of the character set. In this problem, C = 26.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Character Comparison | O(n * m) | O(1) | Useful for understanding the problem or when input sizes are very small |
| Greedy + Hash Table with Position Lists | O(n + m) | O(n + m) | General optimal solution for large strings; minimizes comparisons using indexed character groups |
LeetCode 1794. Count Pairs of Equal Substrings With Minimum Difference | Locked Question • 宰相小甘罗 • 170 views views
Watch 2 more video solutions →Practice Count Pairs of Equal Substrings With Minimum Difference with our built-in code editor and test cases.
Practice on FleetCode