Watch 3 video solutions for Count Pairs of Equal Substrings With Minimum Difference, a medium level problem involving Hash Table, String, Greedy. This walkthrough by 宰相小甘罗 has 170 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |