1794. Count Pairs of Equal Substrings With Minimum Difference

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.

 

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

Rust Solution

struct Solution;

impl Solution {
    fn count_quadruples(first_string: String, second_string: String) -> i32 {
        let first_string: Vec<u8> = first_string.bytes().collect();
        let second_string: Vec<u8> = second_string.bytes().collect();
        let n = first_string.len();
        let m = second_string.len();
        let mut min = std::i32::MAX;
        for j in 0..26 {
            let left = first_string
                .iter()
                .enumerate()
                .filter_map(|(i, &b)| {
                    if b == b'a' + j as u8 {
                        Some(i as i32)
                    } else {
                        None
                    }
                })
                .min();
            let right = second_string
                .iter()
                .enumerate()
                .filter_map(|(i, &b)| {
                    if b == b'a' + j as u8 {
                        Some(i as i32)
                    } else {
                        None
                    }
                })
                .max();
            if let (Some(l), Some(r)) = (left, right) {
                min = min.min(l - r);
            }
        }
        let mut res = 0;
        for i in 0..n {
            let a = first_string[i];
            let j = i as i32 - min;
            if j < m as i32 && j >= 0 {
                let b = second_string[j as usize];
                if a == b {
                    res += 1;
                }
            }
        }
        res
    }
}

#[test]
fn test() {
    let first_string = "abcd".to_string();
    let second_string = "bccda".to_string();
    let res = 1;
    assert_eq!(Solution::count_quadruples(first_string, second_string), res);
    let first_string = "ab".to_string();
    let second_string = "cd".to_string();
    let res = 0;
    assert_eq!(Solution::count_quadruples(first_string, second_string), res);
    let first_string = "xznhzmyk".to_string();
    let second_string = "mxznzn".to_string();
    let res = 2;
    assert_eq!(Solution::count_quadruples(first_string, second_string), res);
}

Having problems with this solution? Click here to submit an issue on github.