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.lengthProblem Overview: You are given a string and multiple queries. For each query range [l, r], count how many substrings inside that range start and end with the same character. The substring can contain any characters in between, but its first and last characters must match.
Approach 1: Brute Force Enumeration (O(n²) per query time, O(1) space)
The direct idea is to generate every substring inside a query range and check whether the first and last characters match. For a range of length k, there are O(k²) substrings. For each pair of indices (i, j) where l ≤ i ≤ j ≤ r, you simply verify s[i] == s[j] and increment the count. This approach uses only constant extra memory but becomes extremely slow for large inputs or many queries. It mainly helps build intuition: any valid substring is defined entirely by choosing two positions with the same character.
Approach 2: Prefix Sum + Character Enumeration (O(26) per query time, O(26·n) space)
The key observation is that a substring is valid if its start and end positions contain the same character. If a character appears k times inside a query range, you can form k * (k + 1) / 2 valid substrings using those positions as start and end. That includes single-character substrings and all pairs of equal characters.
To compute k quickly for every query, build a prefix sum table for each of the 26 lowercase letters. The table stores how many times each character appears up to index i. For a query [l, r], retrieve the frequency of every character using a constant-time prefix subtraction. Then apply the formula k * (k + 1) / 2 and sum the results across all characters.
This turns substring enumeration into simple counting. Instead of scanning the range repeatedly, you compute character frequencies in O(1) and iterate over only 26 possibilities. The approach combines ideas from string processing, array prefix accumulation, and frequency counting often implemented with a hash table or fixed-size array.
Recommended for interviews: The prefix sum + counting approach is what interviewers expect. The brute force method shows you understand the definition of valid substrings, but the optimized solution demonstrates pattern recognition and efficient range counting using prefix sums.
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.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Substring Enumeration | O(n²) per query | O(1) | Useful only for understanding the definition of valid substrings or when constraints are extremely small |
| Prefix Sum + Character Counting | O(26) per query | O(26·n) | Best general solution when many queries exist; quickly computes character frequencies in any range |
leetcode 2955 Number of Same End Substrings - partial sum • Code-Yao • 664 views views
Watch 3 more video solutions →Practice Number of Same-End Substrings with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor