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.

Description Hints 2 Solution Video 13:53

2955. Number of Same-End Substrings

Medium60.6% acceptance2 companiesPremium elsewhere, free here

You are given a 0-indexed string s, and a 2D array of integers queries, where queries[i] = [l_i, r_i] indicates a substring of s starting from the index l_i and ending at the index r_i (both inclusive), i.e. s[l_i..r_i].

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:
1^st query: s[0..0] is "a" which has 1 same-end substring: "a".
2^nd query: s[1..4] is "bcaa" which has 5 same-end substrings: "bcaa", "bcaa", "bcaa", "bcaa", "bcaa".
3^rd query: s[2..5] is "caab" which has 5 same-end substrings: "caab", "caab", "caab", "caab", "caab".
4^th 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 * 10⁴
s consists only of lowercase English letters.
1 <= queries.length <= 3 * 10⁴
queries[i] = [l_i, r_i]
0 <= l_i <= r_i < s.length

Asked at 2 companies

Sprinklr

Google

Topics

Hints open one at a time

Hint 1

If there are t occurrences of a character in a substring, there exists t * (t + 1) / 2 Same-End substrings with that character.

Hint 2

Try to calculate the number of occurrences of a character in a substring in O(1) using partial sum.

13:53

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

"abcaab"
[[0,0],[1,4],[2,5],[0,5]]

Input

"abcd"
[[0,3]]

Your code is saved on this device.Solution