Largest Substring Between Two Equal Characters

Difficulty: Easy | Acceptance: 68.30% | Paid: No Topics: Hash Table, String

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

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

• Examples
• Constraints
• Brute Force
• First and Last Occurrence

Examples

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

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

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.

Brute Force

Intuition Check every possible pair of indices in the string. If the characters at those indices are equal, calculate the distance between them and keep track of the maximum distance found.

Steps

• Initialize a variable max_len to -1.
• Use two nested loops to iterate through the string. The outer loop runs from index i to the end, and the inner loop runs from index j = i + 1 to the end.
• If s[i] is equal to s[j], update max_len with the maximum of its current value and j - i - 1.
• Return max_len.

class Solution:
    def maxLengthBetweenEqualCharacters(self, s: str) -> int:
        max_len = -1
        n = len(s)
        for i in range(n):
            for j in range(i + 1, n):
                if s[i] == s[j]:
                    max_len = max(max_len, j - i - 1)
        return max_len

Complexity

• Time: O(n²)
• Space: O(1)
• Notes: Simple to implement but inefficient for very long strings (though constraints are small here).

First and Last Occurrence

Intuition The longest substring for a specific character will always be between its first occurrence and its last occurrence in the string. We can store the first index where each character appears and then calculate the distance to the current index as we iterate.

Steps

• Create a data structure (like an array of size 26 or a hash map) to store the first occurrence index of each character. Initialize all values to -1.
• Iterate through the string. If the current character’s first occurrence is -1, record the current index as its first occurrence.
• Iterate through the string again. For each character, calculate the distance between the current index and its first occurrence index. Update the maximum length found.
• Return the maximum length.

class Solution:
    def maxLengthBetweenEqualCharacters(self, s: str) -> int:
        first_occurrence = {}
        for i, char in enumerate(s):
            if char not in first_occurrence:
                first_occurrence[char] = i
        
        max_len = -1
        for i, char in enumerate(s):
            if char in first_occurrence:
                max_len = max(max_len, i - first_occurrence[char] - 1)
        return max_len

Complexity

• Time: O(n)
• Space: O(1)
• Notes: We use a fixed-size array of 26 integers regardless of the input size, so space complexity is constant.