Skip to main content
Talentd

Count Pairs of Equal Substrings With Minimum Difference - Solution & Explanation

MediumPremiumFree on FleetCodeHash TableStringGreedy9 min readAsked at: Google
Practice this problem

Problem Statement

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 * 105
  • Both strings consist only of lowercase English letters.

Approach Overview

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

Solution

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Character ComparisonO(n * m)O(1)Useful for understanding the problem or when input sizes are very small
Greedy + Hash Table with Position ListsO(n + m)O(n + m)General optimal solution for large strings; minimizes comparisons using indexed character groups

Video Solution

LeetCode 1794. Count Pairs of Equal Substrings With Minimum Difference | Locked Question • 宰相小甘罗 • 171 views views

Watch 2 more video solutions →

Frequently Asked Questions

Is Count Pairs of Equal Substrings With Minimum Difference easy or hard?
This problem is generally classified as Medium. The brute force idea is simple, but finding the optimal solution requires recognizing that characters can be grouped with a hash table and compared using a greedy pointer technique to avoid O(n*m) comparisons.
Count Pairs of Equal Substrings With Minimum Difference Python/Java solution
The typical implementation builds a dictionary or HashMap from characters to index lists in the second string. Then iterate through the first string and compare positions using pointer movement to update the minimum difference and count. The same logic works in Python, Java, C++, Go, and TypeScript with O(n + m) complexity.
How to solve Count Pairs of Equal Substrings With Minimum Difference in O(n)?
Group indices of characters from the second string using a hash table. For each character in the first string, access the corresponding index list and compare nearby positions using a two‑pointer scan. Since each pointer moves forward at most once per element, the total work across both strings stays linear.
What is the best approach for Count Pairs of Equal Substrings With Minimum Difference?
The most efficient solution uses a Greedy + Hash Table strategy. Store all indices of each character from the second string in a hash table, then scan the first string and compare positions using a two‑pointer technique. This reduces unnecessary comparisons and achieves O(n + m) time complexity.
Is Count Pairs of Equal Substrings With Minimum Difference asked at Google/Amazon/Meta?
Problems involving minimum index differences, hash tables, and efficient string matching patterns are common in interviews at companies like Amazon, Google, and Meta. Variants often appear where candidates must optimize brute force substring or character comparisons using hashing or pointer techniques.
What data structure is used in Count Pairs of Equal Substrings With Minimum Difference?
A hash table (or dictionary) is the main data structure. It maps each character to a list of its indices in one of the strings. These index lists are then processed with a greedy two‑pointer technique to compute minimum differences efficiently.
What is the time complexity of Count Pairs of Equal Substrings With Minimum Difference?
The optimal approach runs in O(n + m) time where n and m are the lengths of the two strings. Building the hash table of character positions takes O(m), and scanning the first string with pointer comparisons takes O(n). Space complexity is O(n + m) for storing indices.

Ready to solve this problem?

Practice Count Pairs of Equal Substrings With Minimum Difference with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Longest Substring Without Repeating Characters