##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1794.html

# 1794. Count Pairs of Equal Substrings With Minimum Difference

Medium

## Description

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 i-th character and ends at the j-th character (inclusive) is equal to the substring of secondString that starts at the a-th character and ends at the b-th 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 * 10^5
• Both strings consist only of lowercase English letters.

## Solution

First, find the minimum possible value j - a. If the equal substrings have lengths greater than 1, then after selecting shorter equal substrings, j - a can be reduced, so to obtain the minimum possible value j - a, always consider substrings with length 1. Find each character’s first occurrence in firstString and each character’s last occurrence in lastString, loop over all characters and find the minimum possible value j - a.

Next, count the number of pairs (j, a) that have the minimum possible value j - a. The number of pairs (j, a) is equal to the number of quadruples (i, j, a, b) since i == j and a == b.

Finally, return the count.

• class Solution {
public int countQuadruples(String firstString, String secondString) {
Map<Character, Integer> map1 = new HashMap<Character, Integer>();
Map<Character, Integer> map2 = new HashMap<Character, Integer>();
int length1 = firstString.length(), length2 = secondString.length();
for (int i = length1 - 1; i >= 0; i--) {
char c = firstString.charAt(i);
map1.put(c, i);
}
for (int i = 0; i < length2; i++) {
char c = secondString.charAt(i);
map2.put(c, i);
}
int minDifference = Integer.MAX_VALUE;
Set<Character> keySet = map1.keySet();
for (char c : keySet) {
int index1 = map1.get(c);
if (map2.containsKey(c)) {
int index2 = map2.get(c);
int difference = index1 - index2;
minDifference = Math.min(minDifference, difference);
}
}
if (minDifference == Integer.MAX_VALUE)
return 0;
for (char c : keySet) {
int index1 = map1.get(c);
if (map2.containsKey(c)) {
int index2 = map2.get(c);
int difference = index1 - index2;
if (difference == minDifference)
}
}
}
}

############

class Solution {
public int countQuadruples(String firstString, String secondString) {
int[] last = new int[26];
for (int i = 0; i < secondString.length(); ++i) {
last[secondString.charAt(i) - 'a'] = i + 1;
}
int ans = 0, mi = 1 << 30;
for (int i = 0; i < firstString.length(); ++i) {
int j = last[firstString.charAt(i) - 'a'];
if (j > 0) {
int t = i - j;
if (mi > t) {
mi = t;
ans = 1;
} else if (mi == t) {
++ans;
}
}
}
return ans;
}
}

• class Solution:
def countQuadruples(self, firstString: str, secondString: str) -> int:
last = {c: i for i, c in enumerate(secondString)}
ans, mi = 0, inf
for i, c in enumerate(firstString):
if c in last:
t = i - last[c]
if mi > t:
mi = t
ans = 1
elif mi == t:
ans += 1
return ans


• class Solution {
public:
int countQuadruples(string firstString, string secondString) {
int last[26] = {0};
for (int i = 0; i < secondString.size(); ++i) {
last[secondString[i] - 'a'] = i + 1;
}
int ans = 0, mi = 1 << 30;
for (int i = 0; i < firstString.size(); ++i) {
int j = last[firstString[i] - 'a'];
if (j) {
int t = i - j;
if (mi > t) {
mi = t;
ans = 1;
} else if (mi == t) {
++ans;
}
}
}
return ans;
}
};

• func countQuadruples(firstString string, secondString string) (ans int) {
last := [26]int{}
for i, c := range secondString {
last[c-'a'] = i + 1
}
mi := 1 << 30
for i, c := range firstString {
j := last[c-'a']
if j > 0 {
t := i - j
if mi > t {
mi = t
ans = 1
} else if mi == t {
ans++
}
}
}
return
}

• function countQuadruples(firstString: string, secondString: string): number {
const last: number[] = new Array(26).fill(0);
for (let i = 0; i < secondString.length; ++i) {
last[secondString.charCodeAt(i) - 97] = i + 1;
}
let [ans, mi] = [0, Infinity];
for (let i = 0; i < firstString.length; ++i) {
const j = last[firstString.charCodeAt(i) - 97];
if (j) {
const t = i - j;
if (mi > t) {
mi = t;
ans = 1;
} else if (mi === t) {
++ans;
}
}
}
return ans;
}