Largest Substring Between Two Equal Characters Python/Java solution

Both Python and Java implementations follow the same idea: track the first index of each character and update the maximum substring length when the character repeats. The logic uses a dictionary in Python or a HashMap/array in Java and runs in O(n) time.

How to solve Largest Substring Between Two Equal Characters in O(n)?

Iterate through the string and store the first occurrence of each character in a hash map. When the same character appears again, calculate the substring length as currentIndex - firstIndex - 1. Track the maximum length during the scan. This single-pass strategy achieves O(n) time complexity.

What is the best approach for Largest Substring Between Two Equal Characters?

The hash map approach is the most efficient and commonly expected solution. Store the first index of each character while scanning the string. When the character appears again, compute the distance between the current index and the stored index minus one. This runs in O(n) time with O(1) space.

Is Largest Substring Between Two Equal Characters asked at Google/Amazon/Meta?

Problems involving string indexing, hash tables, and substring calculations frequently appear in interviews at companies like Amazon and Meta. While this exact problem may not always appear, the pattern of tracking first occurrences with a hash map is common in coding interviews.

What data structure is used in Largest Substring Between Two Equal Characters?

A hash table (or hash map) is the primary data structure used in the optimal solution. It stores the first index where each character appears, allowing constant-time lookups when the character appears again later in the string.

What is the time complexity of Largest Substring Between Two Equal Characters?

The optimal solution 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 the number of possible characters is limited.

Description Hints 2 Solution Video 7:05

1624. Largest Substring Between Two Equal Characters

Q: Is Largest Substring Between Two Equal Characters easy or hard?

Largest Substring Between Two Equal Characters is classified as an Easy problem. The challenge mainly involves understanding how to track the first occurrence of characters and compute the distance efficiently using a hash table.

Easy68.5% acceptance1 company

Given a string s, return the length of the longest substring between two equal characters, excluding the two characters. If there is no such substring return -1.

A substring is a contiguous sequence of characters within a string.

Example 1:

Input: s = "aa"
Output: 0
Explanation: The optimal substring here is an empty substring between the two 'a's.

Example 2:

Input: s = "abca"
Output: 2
Explanation: The optimal substring here is "bc".

Example 3:

Input: s = "cbzxy"
Output: -1
Explanation: There are no characters that appear twice in s.

Constraints:

1 <= s.length <= 300
s contains only lowercase English letters.

Asked at 1 company

Microsoft

Topics

Hash Table String

Hints open one at a time

Hint 1

Try saving the first and last position of each character

Hint 2

Try finding every pair of indexes with equal characters

7:05

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def maxLengthBetweenEqualCharacters(self, s: str) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

"aa"

Input

"abca"

Input

"cbzxy"

Your code is saved on this device.Solution