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.

Examples

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

Solution

Method 1 - Shift-based counting (linear time)

Intuition

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.

Approach

• 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.
• Indices are 0-based; minDiff can be negative.

Code

C++

class Solution {
public:
  long long 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);
    }

    const int 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) return 0;

    long long 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;
  }
};

Go

package main

func countPairs(firstString string, secondString string) int64 {
  n := len(firstString)
  m := len(secondString)
  p1 := make([][]int, 26)
  p2 := make([][]int, 26)

  for i := 0; i < n; i++ {
    c := int(firstString[i]-'a')
    p1[c] = append(p1[c], i)
  }
  for j := 0; j < m; j++ {
    c := int(secondString[j]-'a')
    p2[c] = append(p2[c], j)
  }

  const INF = int(1e9)
  minDiff := INF
  for c := 0; c < 26; c++ {
    if len(p1[c]) > 0 && len(p2[c]) > 0 {
      local := p1[c][0] - p2[c][len(p2[c])-1]
      if local < minDiff {
        minDiff = local
      }
    }
  }

  if minDiff == INF {
    return 0
  }

  var ans int64
  for c := 0; c < 26; c++ {
    if len(p1[c]) == 0 || len(p2[c]) == 0 {
      continue
    }
    local := p1[c][0] - p2[c][len(p2[c])-1]
    if local != minDiff {
      continue
    }
    set := make(map[int]struct{}, len(p2[c])*2)
    for _, a := range p2[c] {
      set[a] = struct{}{}
    }
    for _, i := range p1[c] {
      a := i - minDiff
      if _, ok := set[a]; ok {
        ans++
      }
    }
  }

  return ans
}

Java

import java.util.*;

class Solution {
  public long countPairs(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);

    final int 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;
  }
}

Kotlin

class Solution {
  fun countPairs(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 in 0 until n) p1[firstString[i] - 'a'].add(i)
    for (j in 0 until m) p2[secondString[j] - 'a'].add(j)

    val INF = 1_000_000_000
    var minDiff = INF
    for (c in 0 until 26) {
      if (p1[c].isNotEmpty() && p2[c].isNotEmpty()) {
        val local = p1[c].first() - p2[c].last()
        minDiff = minOf(minDiff, local)
      }
    }

    if (minDiff == INF) return 0L

    var ans = 0L
    for (c in 0 until 26) {
      if (p1[c].isEmpty() || p2[c].isEmpty()) continue
      val local = p1[c].first() - p2[c].last()
      if (local != minDiff) continue
      val s = p2[c].toHashSet()
      for (i in p1[c]) {
        val a = i - minDiff
        if (s.contains(a)) ans++
      }
    }

    return ans
  }
}

Python

class Solution:
  def countPairs(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:
      return 0

    ans = 0
    for c in range(26):
      if not p1[c] or not 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 += 1

    return ans

Rust

pub struct Solution;
impl Solution {
  pub fn count_pairs(first_string: String, second_string: String) -> i64 {
    let n = first_string.len();
    let m = second_string.len();
    let mut p1: Vec<Vec<usize>> = vec![Vec::new(); 26];
    let mut p2: Vec<Vec<usize>> = vec![Vec::new(); 26];
    for (i, ch) in first_string.bytes().enumerate() {
      p1[(ch - b'a') as usize].push(i);
    }
    for (j, ch) in second_string.bytes().enumerate() {
      p2[(ch - b'a') as usize].push(j);
    }

    const INF: isize = 1_000_000_000;
    let mut min_diff: isize = INF;
    for c in 0..26 {
      if !p1[c].is_empty() && !p2[c].is_empty() {
        let local = p1[c][0] as isize - p2[c].last().unwrap().clone() as isize;
        if local < min_diff { min_diff = local; }
      }
    }

    if min_diff == INF { return 0; }

    let mut ans: i64 = 0;
    for c in 0..26 {
      if p1[c].is_empty() || p2[c].is_empty() { continue; }
      let local = p1[c][0] as isize - p2[c].last().unwrap().clone() as isize;
      if local != min_diff { continue; }
      let s: std::collections::HashSet<usize> = p2[c].iter().cloned().collect();
      for &i in &p1[c] {
        let a = (i as isize - min_diff) as usize;
        if s.contains(&a) { ans += 1; }
      }
    }

    ans
  }
}

TypeScript

export class Solution {
  countPairs(firstString: string, secondString: string): number {
  const n = firstString.length;
  const m = secondString.length;
  const p1: number[][] = Array.from({ length: 26 }, () => []);
  const p2: number[][] = Array.from({ length: 26 }, () => []);

  for (let i = 0; i < n; i++) p1[firstString.charCodeAt(i) - 97].push(i);
  for (let j = 0; j < m; j++) p2[secondString.charCodeAt(j) - 97].push(j);

  const INF = 1e9;
  let minDiff = INF;
  for (let c = 0; c < 26; c++) {
    if (p1[c].length > 0 && p2[c].length > 0) {
    const local = p1[c][0] - p2[c][p2[c].length - 1];
    if (local < minDiff) minDiff = local;
    }
  }

  if (minDiff === INF) return 0;

  let ans = 0;
  for (let c = 0; c < 26; c++) {
    if (p1[c].length === 0 || p2[c].length === 0) continue;
    const local = p1[c][0] - p2[c][p2[c].length - 1];
    if (local !== minDiff) continue;
    const s = new Set<number>(p2[c]);
    for (const i of p1[c]) {
    const a = i - minDiff;
    if (s.has(a)) ans++;
    }
  }

  return ans;
  }
}

Complexity

• ⏰ 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.