Count pairs of equal substrings with minimum difference

Hash Table String Greedy

63.9% acceptance

Mar 31, 2026

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.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn count_quadruples(first_string: String, second_string: String) -> i32 {
    let first = first_string.as_bytes();
    let second = second_string.as_bytes();
    let mut min_first = [i32::MAX; 26];
    let mut max_second = [-1i32; 26];
    for (i, &b) in first.iter().enumerate() {
      let c = (b - b'a') as usize;
      min_first[c] = min_first[c].min(i as i32);
    }
    for (i, &b) in second.iter().enumerate() {
      let c = (b - b'a') as usize;
      max_second[c] = max_second[c].max(i as i32);
    }
    let mut min_diff = i32::MAX;
    let mut count = 0;
    for c in 0..26 {
      if min_first[c] != i32::MAX && max_second[c] != -1 {
        let diff = min_first[c] - max_second[c];
        if diff < min_diff {
          min_diff = diff;
          count = 1;
        } else if diff == min_diff {
          count += 1;
        }
      }
    }
    count
  }
}