Watch 10 video solutions for Largest Substring Between Two Equal Characters, a easy level problem involving Hash Table, String. This walkthrough by NeetCodeIO has 11,837 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 300s contains only lowercase English letters.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 | 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. |