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 * 104s consists only of lowercase English letters.1 <= queries.length <= 3 * 104queries[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
| class Solution:
def sameEndSubstringCount(self, s: str, queries: List[List[int]]) -> List[int]:
n = len(s)
cs = set(s)
cnt = {c: [0] * (n + 1) for c in cs}
for i, a in enumerate(s, 1):
for c in cs:
cnt[c][i] = cnt[c][i - 1]
cnt[a][i] += 1
ans = []
for l, r in queries:
t = r - l + 1
for c in cs:
x = cnt[c][r + 1] - cnt[c][l]
t += x * (x - 1) // 2
ans.append(t)
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[] sameEndSubstringCount(String s, int[][] queries) {
int n = s.length();
int[][] cnt = new int[26][n + 1];
for (int j = 1; j <= n; ++j) {
for (int i = 0; i < 26; ++i) {
cnt[i][j] = cnt[i][j - 1];
}
cnt[s.charAt(j - 1) - 'a'][j]++;
}
int m = queries.length;
int[] ans = new int[m];
for (int k = 0; k < m; ++k) {
int l = queries[k][0], r = queries[k][1];
ans[k] = r - l + 1;
for (int i = 0; i < 26; ++i) {
int x = cnt[i][r + 1] - cnt[i][l];
ans[k] += x * (x - 1) / 2;
}
}
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
24
| class Solution {
public:
vector<int> sameEndSubstringCount(string s, vector<vector<int>>& queries) {
int n = s.size();
int cnt[26][n + 1];
memset(cnt, 0, sizeof(cnt));
for (int j = 1; j <= n; ++j) {
for (int i = 0; i < 26; ++i) {
cnt[i][j] = cnt[i][j - 1];
}
cnt[s[j - 1] - 'a'][j]++;
}
vector<int> ans;
for (auto& q : queries) {
int l = q[0], r = q[1];
ans.push_back(r - l + 1);
for (int i = 0; i < 26; ++i) {
int x = cnt[i][r + 1] - cnt[i][l];
ans.back() += x * (x - 1) / 2;
}
}
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
24
25
26
| func sameEndSubstringCount(s string, queries [][]int) []int {
n := len(s)
cnt := make([][]int, 26)
for i := 0; i < 26; i++ {
cnt[i] = make([]int, n+1)
}
for j := 1; j <= n; j++ {
for i := 0; i < 26; i++ {
cnt[i][j] = cnt[i][j-1]
}
cnt[s[j-1]-'a'][j]++
}
var ans []int
for _, q := range queries {
l, r := q[0], q[1]
ans = append(ans, r-l+1)
for i := 0; i < 26; i++ {
x := cnt[i][r+1] - cnt[i][l]
ans[len(ans)-1] += x * (x - 1) / 2
}
}
return ans
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| function sameEndSubstringCount(s: string, queries: number[][]): number[] {
const n: number = s.length;
const cnt: number[][] = Array.from({ length: 26 }, () => Array(n + 1).fill(0));
for (let j = 1; j <= n; j++) {
for (let i = 0; i < 26; i++) {
cnt[i][j] = cnt[i][j - 1];
}
cnt[s.charCodeAt(j - 1) - 'a'.charCodeAt(0)][j]++;
}
const ans: number[] = [];
for (const [l, r] of queries) {
ans.push(r - l + 1);
for (let i = 0; i < 26; i++) {
const x: number = cnt[i][r + 1] - cnt[i][l];
ans[ans.length - 1] += (x * (x - 1)) / 2;
}
}
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
24
| impl Solution {
pub fn same_end_substring_count(s: String, queries: Vec<Vec<i32>>) -> Vec<i32> {
let n = s.len();
let mut cnt: Vec<Vec<i32>> = vec![vec![0; n + 1]; 26];
for j in 1..=n {
for i in 0..26 {
cnt[i][j] = cnt[i][j - 1];
}
cnt[(s.as_bytes()[j - 1] as usize) - (b'a' as usize)][j] += 1;
}
let mut ans: Vec<i32> = Vec::new();
for q in queries.iter() {
let l = q[0] as usize;
let r = q[1] as usize;
let mut t = (r - l + 1) as i32;
for i in 0..26 {
let x = cnt[i][r + 1] - cnt[i][l];
t += (x * (x - 1)) / 2;
}
ans.push(t);
}
ans
}
}
|
