Count Pairs of Equal Substrings With Minimum Difference

Count Pairs of Equal Substrings With Minimum Difference - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: firstString = "abc", secondString = "bc"

› Output: 2

💡 Note: Matching substrings: "b" at (1,1) and (0,0) with j-a=1, "c" at (2,2) and (1,1) with j-a=1. Both achieve minimum j-a=1, so count is 2.

Example 2 — Single Character

$ Input: firstString = "a", secondString = "a"

› Output: 1

💡 Note: Only one match: "a" at (0,0) and (0,0) with j-a=0. This is the minimum, so count is 1.

Example 3 — No Matches

$ Input: firstString = "abc", secondString = "def"

› Output: 0

💡 Note: No common substrings between the two strings, so no valid quadruples exist.

Constraints

1 ≤ firstString.length, secondString.length ≤ 100
firstString and secondString consist only of lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input Strings

firstString = 'abc', secondString = 'bc'

Find Matches

Compare all substring pairs and calculate j-a differences

Count Minimum

Count pairs with minimum j-a value

Key Takeaway

🎯 Key Insight: Group equal substrings and find the minimum j-a difference among all matching pairs

Asked in

G Google 12 a Amazon 8 M Microsoft 6

The key insight is to find all matching substring pairs between the two strings and identify those with minimum j-a difference. Best approach uses a two-pass method: first pass finds the minimum difference, second pass counts occurrences. Time: O(n⁴), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Generate All Quadruples	O(n⁴)	O(1)	Generate all possible quadruples and check conditions
Optimized Two-Pass Approach	O(n⁴)	O(1)	First pass finds minimum difference, second pass counts occurrences
Hash Map Optimization	O(n³)	O(n³)	Group equal substrings by content to efficiently find minimum differences

Brute Force - Generate All Quadruples — Algorithm Steps

Generate all substrings from firstString with indices (i,j)
Generate all substrings from secondString with indices (a,b)
Find matches and calculate j-a for each
Count quadruples with minimum j-a value

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate All Pairs

Create all (i,j) from first string and (a,b) from second string

Compare Substrings

Check if firstString[i:j+1] equals secondString[a:b+1]

Find Minimum j-a

Among matches, find those with smallest j-a value

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int solution(char* firstString, char* secondString) {
    int n1 = strlen(firstString), n2 = strlen(secondString);
    int matches[10000][4];
    int matchCount = 0;
    
    // Find all matching substring pairs with their indices
    for (int i = 0; i < n1; i++) {
        for (int j = i; j < n1; j++) {
            for (int a = 0; a < n2; a++) {
                for (int b = a; b < n2; b++) {
                    int len1 = j - i + 1, len2 = b - a + 1;
                    if (len1 == len2 && strncmp(firstString + i, secondString + a, len1) == 0) {
                        matches[matchCount][0] = i;
                        matches[matchCount][1] = j;
                        matches[matchCount][2] = a;
                        matches[matchCount][3] = b;
                        matchCount++;
                    }
                }
            }
        }
    }
    
    if (matchCount == 0) return 0;
    
    // Find minimum j - a value
    int minDiff = INT_MAX;
    for (int i = 0; i < matchCount; i++) {
        int diff = matches[i][1] - matches[i][2];
        if (diff < minDiff) minDiff = diff;
    }
    
    // Count quadruples with minimum difference
    int count = 0;
    for (int i = 0; i < matchCount; i++) {
        if (matches[i][1] - matches[i][2] == minDiff) count++;
    }
    
    return count;
}

int main() {
    char firstString[1001], secondString[1001];
    fgets(firstString, sizeof(firstString), stdin);
    firstString[strcspn(firstString, "\n")] = 0;
    fgets(secondString, sizeof(secondString), stdin);
    secondString[strcspn(secondString, "\n")] = 0;
    
    int result = solution(firstString, secondString);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n⁴)

Nested loops to generate all quadruples (i,j,a,b) plus string comparison

✓ Linear Growth

Space Complexity

O(1)

Only using variables, no extra data structures

✓ Linear Space

8.5K Views

Medium Frequency

~25 min Avg. Time

234 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Generate All Quadruples — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler