Formatted question description: https://leetcode.ca/all/1794.html
1794. Count Pairs of Equal Substrings With Minimum Difference
Level
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 thei-th
character and ends at thej-th
character (inclusive) is equal to the substring ofsecondString
that starts at thea-th
character and ends at theb-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;
int quadruples = 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)
quadruples++;
}
}
return quadruples;
}
}