1624. Largest Substring Between Two Equal Characters
Model: qwen2.5-coder:14b
Topics:
FAANG asked: 0
Acceptance rate: 58.6%
Problem Breakdown
The problem requires finding the length of the longest substring between two equal characters in a given string s. The substring should exclude the two equal characters themselves. If no such substring exists, return -1.
Inputs:
- A single string
scontaining only lowercase English letters.
Outputs:
- An integer representing the length of the longest substring between two equal characters, or
-1if no such substring exists.
Implicit Constraints and Edge Cases:
- The string can be as short as 1 character.
- If all characters are unique, the output should be
-1. - If there are multiple pairs of equal characters, we need to find the longest one.
- The string length is limited to 300 characters.
Intuition
A brute-force approach would involve checking every possible pair of equal characters and calculating the substring length between them. This would result in a time complexity of O(n^2), which is inefficient given the constraints.
The key insight is to use a dictionary to store the first occurrence index of each character as we iterate through the string. By doing this, we can efficiently calculate the length of the substring between the first and last occurrence of each character. This reduces the time complexity to O(n).
Approach
- Initialize an empty dictionary
first_occurrenceto store the first occurrence index of each character. - Initialize a variable
max_lengthto-1to keep track of the maximum length found. - Iterate through the string using an index
iand characterchar.- If
charis not infirst_occurrence, add it with its current indexi. - If
charis already infirst_occurrence, calculate the substring length between the first occurrence and the current indexi. Updatemax_lengthif this length is greater than the currentmax_length.
- If
- Return
max_length.
Complexity Analysis
- Time Complexity: O(n), where n is the length of the string. We iterate through the string once.
- Space Complexity: O(1) for the dictionary, as it can contain at most 26 entries (one for each lowercase English letter).
Solution
def maxLengthBetweenEqualCharacters(s: str) -> int:
first_occurrence = {}
max_length = -1
for i, char in enumerate(s):
if char not in first_occurrence:
first_occurrence[char] = i
else:
length = i - first_occurrence[char] - 1
max_length = max(max_length, length)
return max_length
Edge Cases Handled
- Single Character String: If the string has only one character,
max_lengthremains-1, as no substring can be formed. - All Unique Characters: The dictionary will store all characters with their first occurrence index, and
max_lengthwill remain-1. - Multiple Pairs of Equal Characters: The algorithm correctly identifies the longest substring between any pair of equal characters.