{x}
blog image

Largest Substring Between Two Equal Characters

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 <= 300
  • s contains only lowercase English letters.

Solution Explanation

The problem asks to find the length of the longest substring between two equal characters in a given string. The solution uses a hash map (or dictionary in Python) to store the index of each character's first appearance. The algorithm iterates through the string, and for each character:

  1. Check if the character exists in the hash map: If it does, this means we've encountered this character before. We calculate the length of the substring between the current index and the previously stored index, and update the maximum length if necessary.

  2. If the character is not in the hash map: We store its index in the hash map for future reference.

Finally, the algorithm returns the maximum length found. If no character appears twice, the maximum length remains -1.

Time and Space Complexity Analysis

  • Time Complexity: O(n), where n is the length of the string. We iterate through the string once. Hash map lookups and insertions are on average O(1).

  • Space Complexity: O(1). The hash map stores at most 26 entries (for lowercase English letters), so the space used is constant regardless of the input string's length. This is because the alphabet size is fixed.

Code Explanation (Python)

The Python code efficiently implements this approach:

class Solution:
    def maxLengthBetweenEqualCharacters(self, s: str) -> int:
        d = {}  # Dictionary to store character indices
        ans = -1  # Initialize maximum length to -1
        for i, c in enumerate(s):  # Iterate through string with index
            if c in d:  # Character already seen
                ans = max(ans, i - d[c] - 1)  # Update max length
            else:
                d[c] = i  # Store index of first occurrence
        return ans

The enumerate function efficiently provides both the index and the value during iteration. The max function elegantly updates the ans variable.

The other languages' code follows a similar logic, adapting the data structures and syntax according to the specific language. The core algorithmic approach remains consistent across all implementations.