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.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.
C++
Java
Python
C#
JavaScript
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).
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n).
Space Complexity: O(1).
| Approach | Complexity |
|---|---|
| Hash Map Approach | Time Complexity: O(n) where n is the length of the string. |
| Two-Pass Approach | Time Complexity: O(n). |
Longest Substring Without Repeating Characters - Leetcode 3 - Python • NeetCode • 657,697 views views
Watch 9 more video solutions →Practice Largest Substring Between Two Equal Characters with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor