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

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].
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).
Return the answer for each query.

Related Tags