Skip to content

1794. Count Pairs of Equal Substrings With Minimum Difference πŸ”’

DifficultyMedium

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

Solutions

Solution 1: Greedy + Hash Table

Thinking

A valid quadruple needs equal substrings and minimal \(j-a\). Equality collapses to a single character: the leftmost occurrence in \(\textit{firstString}\) paired with the rightmost same character in \(\textit{secondString}\).

Map each character of \(\textit{secondString}\) to its last index. Walk \(\textit{firstString}\) and update the global minimum of \(i-\textit{last}[c]\) together with its multiplicity.

The problem actually asks us to find a smallest index \(i\) and a largest index \(j\) such that \(\textit{firstString}[i]\) equals \(\textit{secondString}[j]\), and the value of \(i - j\) is the smallest among all index pairs that meet the conditions.

Therefore, we first use a hash table \(\textit{last}\) to record the index of the last occurrence of each character in \(\textit{secondString}\). Then we traverse \(\textit{firstString}\). For each character \(c\), if \(c\) has appeared in \(\textit{secondString}\), we calculate \(i - \textit{last}[c]\). If the value of \(i - \textit{last}[c]\) is less than the current minimum value, we update the minimum value and set the answer to 1. If the value of \(i - \textit{last}[c]\) equals the current minimum value, we increment the answer by 1.

The time complexity is \(O(m + n)\), and the space complexity is \(O(C)\), where \(m\) and \(n\) are the lengths of \(\textit{firstString}\) and \(\textit{secondString}\) respectively, and \(C\) is the size of the character set. In this problem, \(C = 26\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
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;
}

Comments