Skip to main content
Talentd

Number of Same-End Substrings - Solution & Explanation

MediumPremiumFree on FleetCodeArrayHash TableStringCounting13 min readAsked at: Google, Sprinklr
Practice this problem

Problem Statement

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 * 104
  • s consists only of lowercase English letters.
  • 1 <= queries.length <= 3 * 104
  • queries[i] = [li, ri]
  • 0 <= li <= ri < s.length

Approach Overview

Problem 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.

Solution

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.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Substring EnumerationO(n²) per queryO(1)Useful only for understanding the definition of valid substrings or when constraints are extremely small
Prefix Sum + Character CountingO(26) per queryO(26·n)Best general solution when many queries exist; quickly computes character frequencies in any range

Video Solution

leetcode 2955 Number of Same End Substrings - partial sum • Code-Yao • 665 views views

Watch 3 more video solutions →

Frequently Asked Questions

Is Number of Same-End Substrings easy or hard?
Number of Same-End Substrings is classified as a Medium problem. The difficulty comes from recognizing that substring enumeration can be replaced with frequency counting using prefix sums. Once that insight is clear, the implementation becomes straightforward.
Number of Same-End Substrings Python/Java solution
Implement a 2D prefix array where prefix[i][c] stores how many times character c appears in the first i characters. For each query, compute the frequency of every character in the range and apply the formula k*(k+1)/2. The same logic works in Python, Java, C++, Go, TypeScript, and Rust.
How to solve Number of Same-End Substrings in O(n)?
Build prefix frequency arrays for all characters in the string in O(n). For each query range [l, r], compute how many times each character occurs using prefix subtraction. If a character appears k times in that range, add k*(k+1)/2 to the answer. The preprocessing is O(n) and each query takes O(26) time.
What is the best approach for Number of Same-End Substrings?
The most efficient approach uses prefix sums with character frequency counting. Precompute prefix counts for each of the 26 letters, then for every query calculate how many times each character appears in the range. If a character appears k times, it contributes k*(k+1)/2 substrings. Each query runs in O(26) time.
Is Number of Same-End Substrings asked at Google/Amazon/Meta?
Problems involving prefix sums, substring counting, and frequency arrays appear frequently in interviews at companies like Google, Amazon, and Meta. While this exact problem may vary, the pattern of converting substring enumeration into character frequency counting is a common interview technique.
What data structure is used in Number of Same-End Substrings?
The solution primarily uses prefix sum arrays to store cumulative character frequencies. A fixed-size array of length 26 tracks counts for each lowercase letter. This structure allows constant-time frequency lookup for any query range.
What is the time complexity of Number of Same-End Substrings?
The optimized solution runs in O(26 * q + 26 * n) time where n is the string length and q is the number of queries. Each query iterates through the 26 lowercase letters to compute substring counts. Space complexity is O(26 * n) for the prefix frequency table.

Ready to solve this problem?

Practice Number of Same-End Substrings with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays