Watch 4 video solutions for Number of Same-End Substrings, a medium level problem involving Array, Hash Table, String. This walkthrough by Code-Yao has 664 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |