Watch 2 video solutions for Substrings That Begin and End With the Same Letter, a medium level problem involving Hash Table, Math, String. This walkthrough by Programming Live with Larry has 266 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 consisting of only lowercase English letters. Return the number of substrings in s that begin and end with the same character.
A substring is a contiguous non-empty sequence of characters within a string.
Example 1:
Input: s = "abcba" Output: 7 Explanation: The substrings of length 1 that start and end with the same letter are: "a", "b", "c", "b", and "a". The substring of length 3 that starts and ends with the same letter is: "bcb". The substring of length 5 that starts and ends with the same letter is: "abcba".
Example 2:
Input: s = "abacad" Output: 9 Explanation: The substrings of length 1 that start and end with the same letter are: "a", "b", "a", "c", "a", and "d". The substrings of length 3 that start and end with the same letter are: "aba" and "aca". The substring of length 5 that starts and ends with the same letter is: "abaca".
Example 3:
Input: s = "a" Output: 1 Explanation: The substring of length 1 that starts and ends with the same letter is: "a".
Constraints:
1 <= s.length <= 105s consists only of lowercase English letters.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.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Substring Check | O(n²) | O(1) | Useful for understanding the problem or when constraints are very small |
| Hash Table / Frequency Counting | O(n) | O(1) | Best general solution; single pass counting for large strings |