Substrings That Begin and End With the Same Letter - Solution & Explanation

Problem Overview: Given a string s, count how many substrings start and end with the same character. The substring can contain anything in the middle, but the first and last characters must match.

Approach 1: Brute Force Enumeration (O(n²) time, O(1) space)

Check every possible substring and count the ones whose first and last characters are equal. Use two nested loops: the outer loop picks a start index, and the inner loop expands the end index. For each pair (i, j), verify s[i] == s[j] and increment the count. This approach is simple and demonstrates the problem definition clearly, but it performs roughly n²/2 comparisons in the worst case. It works for small inputs but will struggle with longer strings.

Approach 2: Frequency Counting with Hash Table (O(n) time, O(1) space)

The key observation: every time you encounter a character, you can form new valid substrings with all previous occurrences of the same character. Maintain a frequency map using a hash table or a fixed array of size 26. When processing character c, there are already freq[c] substrings that can end here and start at each earlier occurrence of c. Also count the single-character substring itself. Add freq[c] + 1 to the result, then increment the frequency of c. This effectively counts combinations of matching start and end positions in a single pass.

The method is closely related to counting techniques and prefix-style accumulation patterns often used in prefix sum problems. Instead of generating substrings explicitly, the algorithm counts how many valid start positions exist for each end position.

Recommended for interviews: Interviewers expect the linear-time counting approach. The brute force method shows you understand the problem definition, but the hash table frequency technique demonstrates pattern recognition and the ability to reduce quadratic enumeration to a single pass.