Number of Same-End Substrings

Number of Same-End Substrings

What is this problem about?

The Number of Same-End Substrings problem asks you to count substrings that start and end with the same character. This Number of Same-End Substrings coding problem uses prefix frequency counting to efficiently compute the answer for each ending character.

Why is this asked in interviews?

Sprinklr and Google ask this to test prefix sum combined with frequency counting. For each character c and position i, the number of substrings ending at i with the same first and last character c equals the count of previous occurrences of c in s[0..i-1] plus 1 (the single character). The array, hash table, counting, string, and prefix sum interview pattern is directly applied.

Algorithmic pattern used

Running frequency count. Maintain a frequency array freq[26]. For each position i with character c = s[i]: the substrings starting and ending with c that end at i = freq[c] + 1 (freq[c] previous starts, plus the single character [i..i]). Add this to total. Increment freq[c]. Return total.

Example explanation

s = "abcba".

• i=0, c='a': freq['a']=0. Count += 1. freq['a']=1. Total=1.
• i=1, c='b': freq['b']=0. Count += 1. Total=2.
• i=2, c='c': Count += 1. Total=3.
• i=3, c='b': freq['b']=1. Count += 2. Total=5.
• i=4, c='a': freq['a']=1. Count += 2. Total=7. Answer = 7 same-end substrings: a, ab[b?]... let me list: "a","b","c","b","a","abcba","bcb","bb"... Actually single chars=5, "abcba"(a..a), "bcb"(b..b),"bb"? No, s="abcba". Substrings starting&ending with same char: "a","b","c","b","a","abcba","bcb". That's 7 ✓.

Common mistakes candidates make

• Not including single-character substrings (each counts as 1).
• Computing the answer as freq[c] without adding 1 for the current position.
• Building O(n²) substrings and checking first/last characters.
• Not resetting freq for different test cases.

Interview preparation tip

"Count substrings starting and ending with same character" is a classic prefix frequency problem. For each position, the count contribution = 1 + (previous occurrences of the same character). This O(n) single-pass solution is far more efficient than checking all O(n²) substrings. Practice similar prefix-frequency problems: "count subarrays with equal first and last elements," "count palindromic substrings by character." The running frequency approach generalizes to many substring counting problems.