Problem

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 arrayans where ans[i] is the number ofsame-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.

Examples

Example 1:

1
2
3
4
5
6
7

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: "**_b_** caa", "b** _c_** aa", "bc** _a_** a", "bca** _a_** ", "bc** _aa_** ".
3rd query: s[2..5] is "caab" which has 5 same-end substrings: "**_c_** aab", "c** _a_** ab", "ca** _a_** b", "caa** _b_** ", "c** _aa_** b".
4th query: s[0..5] is "abcaab" which has 10 same-end substrings: "**_a_** bcaab", "a** _b_** caab", "ab** _c_** aab", "abc** _a_** ab", "abca** _a_** b", "abcaa** _b_** ", "abc** _aa_** b", "**_abca_** ab", "**_abcaa_** b", "a** _bcaab_** ".

Example 2:

1
2
3

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: "**_a_** bcd", "a** _b_** cd", "ab** _c_** d", "abc** _d_** ".

Constraints:

  • 2 <= s.length <= 3 * 10^4
  • s consists only of lowercase English letters.
  • 1 <= queries.length <= 3 * 10^4
  • queries[i] = [li, ri]
  • 0 <= li <= ri < s.length

Solution

Method 1 – Prefix Frequency and Counting

Intuition

For a substring, the number of same-end substrings is the sum over all characters of the number of ways to pick two positions (or one) with that character at both ends. We can precompute prefix sums for each character to answer each query efficiently.

Approach

  1. For each character ‘a’ to ‘z’, build a prefix sum array pre[c][i] = number of times character c appears in s[0..i-1].
  2. For each query [l, r]:
    • For each character c, count = pre[c][r+1] - pre[c][l].
    • For each count, add count (for single-letter substrings) and count*(count-1)//2 (for substrings with same char at both ends).
  3. Return the answer for each query.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include <vector>
#include <string>
using namespace std;
class Solution {
public:
    vector<int> sameEndSubstrings(string s, vector<vector<int>>& queries) {
        int n = s.size();
        vector<vector<int>> pre(26, vector<int>(n+1, 0));
        for (int i = 0; i < n; ++i) {
            for (int c = 0; c < 26; ++c) pre[c][i+1] = pre[c][i];
            pre[s[i]-'a'][i+1]++;
        }
        vector<int> ans;
        for (auto& q : queries) {
            int l = q[0], r = q[1], res = 0;
            for (int c = 0; c < 26; ++c) {
                int cnt = pre[c][r+1] - pre[c][l];
                res += cnt + cnt*(cnt-1)/2;
            }
            ans.push_back(res);
        }
        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

func sameEndSubstrings(s string, queries [][]int) []int {
    n := len(s)
    pre := make([][]int, 26)
    for i := range pre {
        pre[i] = make([]int, n+1)
    }
    for i := 0; i < n; i++ {
        for c := 0; c < 26; c++ {
            pre[c][i+1] = pre[c][i]
        }
        pre[s[i]-'a'][i+1]++
    }
    ans := make([]int, len(queries))
    for qi, q := range queries {
        l, r, res := q[0], q[1], 0
        for c := 0; c < 26; c++ {
            cnt := pre[c][r+1] - pre[c][l]
            res += cnt + cnt*(cnt-1)/2
        }
        ans[qi] = res
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    public int[] sameEndSubstrings(String s, int[][] queries) {
        int n = s.length();
        int[][] pre = new int[26][n+1];
        for (int i = 0; i < n; ++i) {
            for (int c = 0; c < 26; ++c) pre[c][i+1] = pre[c][i];
            pre[s.charAt(i)-'a'][i+1]++;
        }
        int[] ans = new int[queries.length];
        for (int qi = 0; qi < queries.length; ++qi) {
            int l = queries[qi][0], r = queries[qi][1], res = 0;
            for (int c = 0; c < 26; ++c) {
                int cnt = pre[c][r+1] - pre[c][l];
                res += cnt + cnt*(cnt-1)/2;
            }
            ans[qi] = res;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    fun sameEndSubstrings(s: String, queries: Array<IntArray>): IntArray {
        val n = s.length
        val pre = Array(26) { IntArray(n+1) }
        for (i in 0 until n) {
            for (c in 0 until 26) pre[c][i+1] = pre[c][i]
            pre[s[i]-'a'][i+1]++
        }
        val ans = IntArray(queries.size)
        for ((qi, q) in queries.withIndex()) {
            val (l, r) = q
            var res = 0
            for (c in 0 until 26) {
                val cnt = pre[c][r+1] - pre[c][l]
                res += cnt + cnt*(cnt-1)/2
            }
            ans[qi] = res
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
    def sameEndSubstrings(self, s: str, queries: list[list[int]]) -> list[int]:
        n = len(s)
        pre = [[0]*(n+1) for _ in range(26)]
        for i, ch in enumerate(s):
            for c in range(26):
                pre[c][i+1] = pre[c][i]
            pre[ord(ch)-97][i+1] += 1
        ans = []
        for l, r in queries:
            res = 0
            for c in range(26):
                cnt = pre[c][r+1] - pre[c][l]
                res += cnt + cnt*(cnt-1)//2
            ans.append(res)
        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

impl Solution {
    pub fn same_end_substrings(s: String, queries: Vec<Vec<i32>>) -> Vec<i32> {
        let n = s.len();
        let s = s.as_bytes();
        let mut pre = vec![vec![0; n+1]; 26];
        for i in 0..n {
            for c in 0..26 { pre[c][i+1] = pre[c][i]; }
            pre[(s[i]-b'a') as usize][i+1] += 1;
        }
        let mut ans = vec![];
        for q in queries {
            let l = q[0] as usize;
            let r = q[1] as usize;
            let mut res = 0;
            for c in 0..26 {
                let cnt = pre[c][r+1] - pre[c][l];
                res += cnt + cnt*(cnt-1)/2;
            }
            ans.push(res as i32);
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    sameEndSubstrings(s: string, queries: number[][]): number[] {
        const n = s.length;
        const pre = Array.from({length:26},()=>Array(n+1).fill(0));
        for (let i = 0; i < n; ++i) {
            for (let c = 0; c < 26; ++c) pre[c][i+1] = pre[c][i];
            pre[s.charCodeAt(i)-97][i+1]++;
        }
        const ans = [];
        for (const [l, r] of queries) {
            let res = 0;
            for (let c = 0; c < 26; ++c) {
                const cnt = pre[c][r+1] - pre[c][l];
                res += cnt + cnt*(cnt-1)/2;
            }
            ans.push(res);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O((n+q)*26), where n is the length of s and q is the number of queries. Preprocessing and each query are both O(26).
  • 🧺 Space complexity: O(n*26), for the prefix sum arrays.