Largest Substring Between Two Equal Characters - Solution & Explanation
Problem Statement
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 <= 300scontains only lowercase English letters.
Approach Overview
Problem Overview: You receive a string s. The goal is to find the length of the largest substring that lies strictly between two equal characters. Only the characters between the pair count. If no such pair exists, return -1.
Approach 1: Hash Map (O(n) time, O(1) space)
Track the first occurrence of every character while scanning the string from left to right. Use a hash table that maps each character to its earliest index. When you encounter the same character again at index i, compute the substring length as i - firstIndex - 1. Update the maximum length if this value is larger. Because the alphabet size is limited (typically lowercase English letters), the extra space remains constant.
The key insight: the longest substring for a character always occurs between its first appearance and the farthest later occurrence. Storing only the first index guarantees the maximum gap when the character appears again.
Approach 2: Two-Pass Approach (O(n) time, O(1) space)
This method separates discovery of character positions from computing distances. In the first pass, record the first index where each character appears. In the second pass, update the last index seen for each character and compute the distance between the first and current position. The substring length is again last - first - 1. This approach still runs in linear time and uses constant extra memory due to the small alphabet.
The logic relies entirely on simple array or map lookups and sequential scans of the string. No nested loops are required, which keeps the solution efficient even for large inputs.
Recommended for interviews: The hash map approach is the expected solution. It shows you recognize the pattern of storing first occurrences and performing constant-time lookups during a single pass. Interviewers often accept the two-pass version as well, but the single-pass hash table solution demonstrates stronger algorithmic instinct and cleaner implementation.
Approach 1: Hash Map Approach
This approach uses a hash map to store the first and last occurrence of each character as you traverse the string. For each character, calculate the distance between its occurrences and keep track of the maximum distance found. This efficiently provides the length of the longest substring between two identical characters.
This code initializes an array to track the first occurrence of each character. It iterates through the string, updating the maximum length between identical characters by checking current indices against their recorded first occurrence.
Complexity
Time Complexity: O(n) where n is the length of the string.
Space Complexity: O(1) since the hash map size is constant (fixed at 256 for all possible lowercase characters).
Approach 2: Two-Pass Approach
This approach involves two pass-throughs of the string. The first pass records each character's first occurrence, while the second calculates potential maximum lengths using each character's last occurrence.
In this C code, two arrays are used for first and last occurrence tracking. The two-pass approach ensures we retain needed indices to measure lengths effectively.
Complexity
Time Complexity: O(n).
Space Complexity: O(1).
Approach 3: Default Approach
Try this approach in the editor →Complexity Comparison
| Approach | Complexity |
|---|---|
| Hash Map Approach | Time Complexity: O(n) where n is the length of the string. |
| Two-Pass Approach | Time Complexity: O(n). |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hash Map | O(n) | O(1) | Best general solution. Single pass with constant-time lookups. |
| Two-Pass Approach | O(n) | O(1) | Useful when separating position tracking and distance calculation improves readability. |
Video Solution
Largest Substring Between Two Equal Characters - Leetcode 1624 - Python • NeetCodeIO • 11,982 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Largest Substring Between Two Equal Characters easy or hard?
Largest Substring Between Two Equal Characters Python/Java solution
How to solve Largest Substring Between Two Equal Characters in O(n)?
What is the best approach for Largest Substring Between Two Equal Characters?
Is Largest Substring Between Two Equal Characters asked at Google/Amazon/Meta?
What data structure is used in Largest Substring Between Two Equal Characters?
What is the time complexity of Largest Substring Between Two Equal Characters?
Ready to solve this problem?
Practice Largest Substring Between Two Equal Characters with our built-in code editor and test cases.
Practice on FleetCode