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.
Input: firstString ="abcd", secondString ="bccda"Output: 1Explanation: The quadruple(0,0,4,4)is the only one that satisfies all the conditions and minimizes j - a.
For any matching substring pair that starts at i in firstString and at a in secondString, the value j - a (where j = i + L - 1) equals (i - a) + (L - 1). For fixed start indices (i, a), longer matches only increase j - a. Therefore the global minimum j - a must come from a single-character match (length L = 1) that minimizes i - a. Thus we only need to find the smallest value of i - a among all equal-character pairs and count how many single-character matches achieve that difference.
This observation yields an O(n + m) algorithm by grouping positions of each character and checking starts efficiently.
Build arrays of indices for each character c in firstString and secondString.
For each character c present in both strings, the minimal i - a for that character equals minIndexInFirst[c] - maxIndexInSecond[c] (pick the smallest i and largest a).
Global minDiff is the minimum of those values across characters.
To count matches achieving minDiff, for each character c with minIndexInFirst[c] - maxIndexInSecond[c] == minDiff, check for every index i in firstString with character c whether a = i - minDiff exists in secondString’s indices (use a hash-set for lookups). Each such occurrence contributes one valid quadruple (single-character substring).
Edge cases:
If no character appears in both strings, the answer is 0.
classSolution {
public:longlong countPairs(string firstString, string secondString) {
int n = firstString.size();
int m = secondString.size();
vector<vector<int>> p1(26), p2(26);
for (int i =0; i < n; ++i) {
p1[firstString[i] -'a'].push_back(i);
}
for (int j =0; j < m; ++j) {
p2[secondString[j] -'a'].push_back(j);
}
constint INF =1e9;
int minDiff = INF;
for (int c =0; c <26; ++c) {
if (!p1[c].empty() &&!p2[c].empty()) {
int local = p1[c].front() - p2[c].back();
if (local < minDiff) minDiff = local;
}
}
if (minDiff == INF) return0;
longlong ans =0;
for (int c =0; c <26; ++c) {
if (p1[c].empty() || p2[c].empty()) continue;
int local = p1[c].front() - p2[c].back();
if (local != minDiff) continue;
unordered_set<int> s;
s.reserve(p2[c].size() *2);
for (int a : p2[c]) s.insert(a);
for (int i : p1[c]) {
int a = i - minDiff;
if (s.find(a) != s.end()) ++ans;
}
}
return ans;
}
};
import java.util.*;
classSolution {
publiclongcountPairs(String firstString, String secondString) {
int n = firstString.length();
int m = secondString.length();
List<Integer>[] p1 =new ArrayList[26];
List<Integer>[] p2 =new ArrayList[26];
for (int i = 0; i < 26; ++i) { p1[i]=new ArrayList<>(); p2[i]=new ArrayList<>(); }
for (int i = 0; i < n; ++i) p1[firstString.charAt(i) -'a'].add(i);
for (int j = 0; j < m; ++j) p2[secondString.charAt(j) -'a'].add(j);
finalint INF = 1_000_000_000;
int minDiff = INF;
for (int c = 0; c < 26; ++c) {
if (!p1[c].isEmpty() &&!p2[c].isEmpty()) {
int local = p1[c].get(0) - p2[c].get(p2[c].size() - 1);
minDiff = Math.min(minDiff, local);
}
}
if (minDiff == INF) return 0;
long ans = 0;
for (int c = 0; c < 26; ++c) {
if (p1[c].isEmpty() || p2[c].isEmpty()) continue;
int local = p1[c].get(0) - p2[c].get(p2[c].size() - 1);
if (local != minDiff) continue;
Set<Integer> s =new HashSet<>(p2[c]);
for (int i : p1[c]) {
int a = i - minDiff;
if (s.contains(a)) ans++;
}
}
return ans;
}
}
classSolution {
funcountPairs(firstString: String, secondString: String): Long {
val n = firstString.length
val m = secondString.length
val p1 = Array(26) { mutableListOf<Int>() }
val p2 = Array(26) { mutableListOf<Int>() }
for (i in0 until n) p1[firstString[i] - 'a'].add(i)
for (j in0 until m) p2[secondString[j] - 'a'].add(j)
val INF = 1_000_000_000
var minDiff = INF
for (c in0 until 26) {
if (p1[c].isNotEmpty() && p2[c].isNotEmpty()) {
val local = p1[c].first() - p2[c].last()
minDiff = minOf(minDiff, local)
}
}
if (minDiff == INF) return0Lvar ans = 0Lfor (c in0 until 26) {
if (p1[c].isEmpty() || p2[c].isEmpty()) continueval local = p1[c].first() - p2[c].last()
if (local != minDiff) continueval s = p2[c].toHashSet()
for (i in p1[c]) {
val a = i - minDiff
if (s.contains(a)) ans++ }
}
return ans
}
}
classSolution:
defcountPairs(self, firstString: str, secondString: str) -> int:
p1: list[list[int]] = [[] for _ in range(26)]
p2: list[list[int]] = [[] for _ in range(26)]
for i, ch in enumerate(firstString):
p1[ord(ch) - ord('a')].append(i)
for j, ch in enumerate(secondString):
p2[ord(ch) - ord('a')].append(j)
INF =10**9 min_diff = INF
for c in range(26):
if p1[c] and p2[c]:
local = p1[c][0] - p2[c][-1]
if local < min_diff:
min_diff = local
if min_diff == INF:
return0 ans =0for c in range(26):
ifnot p1[c] ornot p2[c]:
continue local = p1[c][0] - p2[c][-1]
if local != min_diff:
continue s = set(p2[c])
for i in p1[c]:
a = i - min_diff
if a in s:
ans +=1return ans
pubstructSolution;
impl Solution {
pubfncount_pairs(first_string: String, second_string: String) -> i64 {
let n = first_string.len();
let m = second_string.len();
letmut p1: Vec<Vec<usize>>=vec![Vec::new(); 26];
letmut p2: Vec<Vec<usize>>=vec![Vec::new(); 26];
for (i, ch) in first_string.bytes().enumerate() {
p1[(ch -b'a') asusize].push(i);
}
for (j, ch) in second_string.bytes().enumerate() {
p2[(ch -b'a') asusize].push(j);
}
constINF: isize=1_000_000_000;
letmut min_diff: isize=INF;
for c in0..26 {
if!p1[c].is_empty() &&!p2[c].is_empty() {
let local = p1[c][0] asisize- p2[c].last().unwrap().clone() asisize;
if local < min_diff { min_diff = local; }
}
}
if min_diff ==INF { return0; }
letmut ans: i64=0;
for c in0..26 {
if p1[c].is_empty() || p2[c].is_empty() { continue; }
let local = p1[c][0] asisize- p2[c].last().unwrap().clone() asisize;
if local != min_diff { continue; }
let s: std::collections::HashSet<usize>= p2[c].iter().cloned().collect();
for&i in&p1[c] {
let a = (i asisize- min_diff) asusize;
if s.contains(&a) { ans +=1; }
}
}
ans
}
}
⏰ Time complexity: O(n + m) where n = firstString.length and m = secondString.length — we scan both strings once to collect indices and then perform constant-time checks per index.
🧺 Space complexity: O(n + m) for storing index lists for each character.