2955. Number of Same-End Substrings π
Description
You are given a 0-indexed string s
, and a 2D array of integers queries
, where queries[i] = [li, ri]
indicates a substring of s
starting from the index li
and ending at the index ri
(both inclusive), i.e. s[li..ri]
.
Return an array ans
where ans[i]
is the number of same-end substrings of queries[i]
.
A 0-indexed string t
of length n
is called same-end if it has the same character at both of its ends, i.e., t[0] == t[n - 1]
.
A substring is a contiguous non-empty sequence of characters within a string.
Example 1:
Input: s = "abcaab", queries = [[0,0],[1,4],[2,5],[0,5]] Output: [1,5,5,10] Explanation: Here is the same-end substrings of each query: 1st query: s[0..0] is "a" which has 1 same-end substring: "a". 2nd query: s[1..4] is "bcaa" which has 5 same-end substrings: "bcaa", "bcaa", "bcaa", "bcaa", "bcaa". 3rd query: s[2..5] is "caab" which has 5 same-end substrings: "caab", "caab", "caab", "caab", "caab". 4th query: s[0..5] is "abcaab" which has 10 same-end substrings: "abcaab", "abcaab", "abcaab", "abcaab", "abcaab", "abcaab", "abcaab", "abcaab", "abcaab", "abcaab".
Example 2:
Input: s = "abcd", queries = [[0,3]] Output: [4] Explanation: The only query is s[0..3] which is "abcd". It has 4 same-end substrings: "abcd", "abcd", "abcd", "abcd".
Constraints:
2 <= s.length <= 3 * 104
s
consists only of lowercase English letters.1 <= queries.length <= 3 * 104
queries[i] = [li, ri]
0 <= li <= ri < s.length
Solutions
Solution 1: Prefix Sum + Enumeration
We can preprocess the prefix sum for each letter and record it in the array $cnt$, where $cnt[i][j]$ represents the number of times the $i$-th letter appears in the first $j$ characters. In this way, for each interval $[l, r]$, we can enumerate each letter $c$ in the interval, quickly calculate the number of times $c$ appears in the interval $x$ using the prefix sum array. We can arbitrarily choose two of them to form a tail-equal substring, the number of substrings is $C_x^2=\frac{x(x-1)}{2}$, plus the situation where each letter in the interval can form a tail-equal substring alone, there are $r - l + 1$ letters in total. Therefore, for each query $[l, r]$, the number of tail-equal substrings that meet the conditions is $r - l + 1 + \sum_{c \in \Sigma} \frac{x_c(x_c-1)}{2}$, where $x_c$ represents the number of times the letter $c$ appears in the interval $[l, r]$.
The time complexity is $O((n + m) \times |\Sigma|)$, and the space complexity is $O(n \times |\Sigma|)$. Here, $n$ and $m$ are the lengths of the string $s$ and the number of queries, respectively, and $\Sigma$ represents the set of letters appearing in the string $s$, in this problem $|\Sigma|=26$.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
|