Skip to main content
Talentd

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

MediumPremiumFree on FleetCodeHash TableMathStringCounting7 min read
Practice this problem

Problem Statement

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 <= 105
  • s consists only of lowercase English letters.

Approach Overview

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.

Solution

We can use a hash table or an array cnt of length 26 to record the occurrences of each character.

Traverse the string s. For each character c, increment the value of cnt[c] by 1, and then add the value of cnt[c] to the answer.

Finally, return the answer.

The time complexity is O(n), where n is the length of the string s. The space complexity is O(|\Sigma|), where \Sigma is the character set. Here, it is lowercase English letters, so |\Sigma|=26.

Code

PythonJavaC++GoTypeScriptRustJavaScript

Python

Java

C++

Go

TypeScript

Rust

JavaScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Substring CheckO(n²)O(1)Useful for understanding the problem or when constraints are very small
Hash Table / Frequency CountingO(n)O(1)Best general solution; single pass counting for large strings

Video Solution

2083. Substrings That Begin and End With the Same Letter - Week 2/5 Leetcode June Challenge • Programming Live with Larry • 279 views views

Watch 1 more video solutions →

Frequently Asked Questions

Is Substrings That Begin and End With the Same Letter easy or hard?
The problem is rated Medium on LeetCode but the core insight is simple once recognized. A naive O(n²) solution is straightforward, while the optimized O(n) counting approach requires recognizing the frequency accumulation pattern.
Substrings That Begin and End With the Same Letter Python/Java solution
Both Python and Java implementations follow the same idea: maintain a frequency map of characters and accumulate freq[c] + 1 for each character visited. The algorithm runs in O(n) time and requires only constant additional space.
How to solve Substrings That Begin and End With the Same Letter in O(n)?
Traverse the string once while maintaining a frequency map for characters. For each character c, add freq[c] + 1 to the answer because every previous occurrence of c forms a valid substring ending here, plus the single-character substring. Then increment freq[c]. This counts all valid substrings in linear time.
What is the best approach for Substrings That Begin and End With the Same Letter?
The optimal approach uses frequency counting with a hash table or fixed-size array. As you scan the string, track how many times each character has appeared. Each new occurrence contributes freq[c] + 1 valid substrings. This reduces the problem to a single O(n) pass with O(1) extra space.
Is Substrings That Begin and End With the Same Letter asked at Google/Amazon/Meta?
String counting and hash table frequency problems are common in interviews at companies like Amazon, Google, and Meta. Variants involving substring counting, prefix accumulation, and character frequency analysis appear frequently in coding interviews.
What data structure is used in Substrings That Begin and End With the Same Letter?
The main data structure is a hash table or a fixed-size array used to store character frequencies. Since the input consists of lowercase letters, many implementations use an array of size 26 for constant-time updates and lookups.
What is the time complexity of Substrings That Begin and End With the Same Letter?
The optimal algorithm runs in O(n) time where n is the length of the string. Each character is processed once and hash table lookups are constant time. Space complexity is O(1) because only character frequencies are stored.

Ready to solve this problem?

Practice Substrings That Begin and End With the Same Letter with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count Pairs in Two Arrays

Next

Number of Good Pairs