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.

Description Hints 5 Solution Video 10:38

2083. Substrings That Begin and End With the Same Letter

Medium74.1% acceptancePremium elsewhere, free here

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

Topics

Hints open one at a time

Hint 1

In the string "abacad", the letter "a" appears 3 times. How many substrings begin with the first "a" and end with any "a"?

Hint 2

There are 3 substrings ("a", "aba", and "abaca"). How many substrings begin with the second "a" and end with any "a"? How about the third?

Hint 3

2 substrings begin with the second "a" ("a", and "aca") and 1 substring begins with the third "a" ("a").

Hint 4

There is a total of 3 + 2 + 1 = 6 substrings that begin and end with "a".

Hint 5

If a character appears i times in the string, there are i * (i + 1) / 2 substrings that begin and end with that character.

10:38

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

Open solution

2083. Substrings That Begin and End With the Same Letter

Topics

Hints open one at a time

Similar problems