We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count Pairs of Equal Substrings With Minimum Difference

Number: 1943

Difficulty: Medium

Paid? Yes

Companies: Google

Problem Description

You are given two 0-indexed strings, firstString and secondString, consisting of lowercase English letters. We want to count the number of quadruples (i, j, a, b) such that: • 0 <= i <= j < firstString.length
• 0 <= a <= b < secondString.length
• The substring firstString[i...j] equals the substring secondString[a...b]
• Among all quadruples that satisfy the above conditions, j - a is as small as possible.
Return the number of quadruples achieving this minimum difference.

Key Insights

  • For any valid quadruple, if the substrings are equal then their lengths are identical. In that situation j = i + (length-1) and b = a + (length-1), so j - a = (i - a) + (length - 1).
  • Since (length - 1) is nonnegative, for fixed starting indices i and a the minimal j - a is obtained by taking the shortest possible substring, i.e. length = 1.
  • Hence the problem reduces to finding all pairs (i, a) such that firstString[i] equals secondString[a] and minimizing the value (i - a). The optimal quadruple corresponds to choosing length = 1 where j = i and b = a.
  • For every letter, the smallest possible difference (i - a) comes by taking the smallest index i in firstString (for that letter) together with the largest index a in secondString (for that letter).
  • Finally, the global minimum difference M is the minimum over all letters (for which the letter exists in both strings) of (min_index_in_first - max_index_in_second). Only the letter(s) that achieve this value contribute one quadruple each.

Space and Time Complexity

Time Complexity: O(n)
 • We make one pass over firstString and secondString to record indices per letter (n = maximum length of input strings).
Space Complexity: O(n)
 • Storing lists of indices for each character (the total number of stored indices is linear in the length of the strings).

Solution

We first build two mappings (or arrays) that record the indices for each letter in firstString and secondString. For each letter that appears in both strings, we compute candidate = (minimum index in firstString for that letter) - (maximum index in secondString for that letter). The global minimum M is the smallest candidate among all letters present in both strings. Since the minimal substring achieving equality is of length 1, the quadruple is uniquely determined by the pair (i, a) achieving that candidate difference. Thus, for every letter whose (min_index - max_index) equals M, we count one valid quadruple. If no letter occurs in both strings, the answer is 0.

Key data structures include: • Two dictionaries (or fixed arrays of size 26) to track lists of indices for each letter in each string. • Iteration over the 26 lowercase letters to compute the candidate differences.

The “greedy” insight is that to minimize j - a, we always want to use the smallest possible i and the largest possible a. This is because j - a is (i - a) plus a constant (0 when substring length is 1). The hash table (or array keyed by letter) efficiently groups indices for each letter.

Code Solutions

Below are code solutions in four languages.

# Python solution with line-by-line comments
def count_min_diff_quadruples(firstString, secondString):
    # Dictionaries to record the indices for each character in firstString and secondString.
    first_indices = {chr(c): [] for c in range(ord('a'), ord('z') + 1)}
    second_indices = {chr(c): [] for c in range(ord('a'), ord('z') + 1)}
    
    # Record indices from firstString.
    for i, ch in enumerate(firstString):
        first_indices[ch].append(i)
    
    # Record indices from secondString.
    for i, ch in enumerate(secondString):
        second_indices[ch].append(i)
    
    global_min = float('inf')  # global minimum candidate value for (i - a)
    # For each character, we compute candidate = (min index in first) - (max index in second).
    for ch in first_indices:
        if first_indices[ch] and second_indices[ch]:
            candidate = first_indices[ch][0] - second_indices[ch][-1]
            if candidate < global_min:
                global_min = candidate

    # If global_min was not updated, no common character exists.
    if global_min == float('inf'):
        return 0

    count = 0
    # Count how many letters achieve the global minimum difference.
    for ch in first_indices:
        if first_indices[ch] and second_indices[ch]:
            if first_indices[ch][0] - second_indices[ch][-1] == global_min:
                count += 1

    return count

# Example usage:
print(count_min_diff_quadruples("abcd", "bccda"))  # Output: 1
print(count_min_diff_quadruples("ab", "cd"))         # Output: 0
← Back to All Questions