Problem Description

You are given a string s and need to find the length of the longest substring that lies between two equal characters, where the substring does not include those two equal characters themselves.

For example, if you have the string "abca", the character 'a' appears at positions 0 and 3. The substring between these two 'a' characters is "bc", which has length 2.

The task requires you to:

• Find any two positions in the string where the same character appears
• Calculate the length of the substring between these two occurrences (excluding the characters themselves)
• Return the maximum such length among all possible pairs of equal characters
• If no character appears more than once in the string, return -1

The solution uses a dictionary to track the first occurrence of each character. When the same character is encountered again, it calculates the distance between the current position and the first occurrence (minus 1 to exclude the characters themselves), keeping track of the maximum distance found.

For instance:

• Input: "aa" → Output: 0 (nothing between the two 'a's)
• Input: "abca" → Output: 2 (substring "bc" between the two 'a's)
• Input: "cbzxy" → Output: -1 (no repeated characters)

Intuition

The key insight is that to find the longest substring between two equal characters, we need to maximize the distance between any two occurrences of the same character.

Think about it this way: if a character appears multiple times in the string, the longest possible substring between two instances of that character would be between its first and last occurrences. Any other pair of positions would give us a shorter or equal length substring.

This leads us to a simple strategy:

1. We only need to remember the first position where each character appears
2. When we encounter a character we've seen before, we calculate the distance from its first occurrence to the current position
3. The substring length between them is current_position - first_position - 1 (we subtract 1 to exclude both characters)

Why does this work? Because as we traverse the string from left to right:

• The first time we see a character, we store its position
• Every subsequent time we see that same character, we're automatically finding a potentially longer substring (since the current position is further from the stored first position)
• We keep updating our answer with the maximum length found so far

For example, if character 'a' appears at positions 0, 3, and 7:

• When we see it at position 3: substring length = 3 - 0 - 1 = 2
• When we see it at position 7: substring length = 7 - 0 - 1 = 6
• The second calculation automatically gives us the longer substring

This approach is efficient because we only need one pass through the string and constant time lookups in our dictionary.

Solution Approach

The solution uses a hash map (dictionary) to track the first occurrence of each character and a single pass through the string to find the maximum distance.

Implementation Steps:

1. Initialize data structures:

   • Create an empty dictionary d to store the first occurrence index of each character
   • Set ans = -1 as the default return value (for when no repeated characters exist)

2. Traverse the string with enumeration:

   for i, c in enumerate(s):

   This gives us both the index i and character c at each position.

3. Check if character has been seen before:

   • If c in d: The character has appeared before
     • Calculate the substring length: i - d[c] - 1
       • i is the current position
       • d[c] is the first occurrence position
       • Subtract 1 to exclude both characters
     • Update ans with the maximum: ans = max(ans, i - d[c] - 1)
   • If c not in d: This is the first occurrence
     • Store the current position: d[c] = i
     • This position will be used for all future occurrences of this character

4. Return the result:

   • After processing all characters, ans contains the maximum length found
   • If no character appeared twice, ans remains -1

Example Walkthrough with s = "abca":

• i=0, c='a': Not in d, store d['a'] = 0
• i=1, c='b': Not in d, store d['b'] = 1
• i=2, c='c': Not in d, store d['c'] = 2
• i=3, c='a': Found in d! Calculate 3 - 0 - 1 = 2, update ans = 2
• Return 2

Time Complexity: O(n) where n is the length of the string (single pass)
Space Complexity: O(min(n, 26)) for the dictionary (at most 26 lowercase letters or n unique characters)

Example Walkthrough

Let's walk through the solution with the string s = "cabbac".

Initial Setup:

• d = {} (empty dictionary to store first occurrences)
• ans = -1 (default return value)

Step-by-step traversal:

i=0, c='c':

• 'c' is not in dictionary
• Store first occurrence: d['c'] = 0
• Dictionary: {'c': 0}
• ans = -1

i=1, c='a':

• 'a' is not in dictionary
• Store first occurrence: d['a'] = 1
• Dictionary: {'c': 0, 'a': 1}
• ans = -1

i=2, c='b':

• 'b' is not in dictionary
• Store first occurrence: d['b'] = 2
• Dictionary: {'c': 0, 'a': 1, 'b': 2}
• ans = -1

i=3, c='b':

• 'b' is in dictionary at position 2!
• Calculate substring length: 3 - 2 - 1 = 0
• The substring between the two 'b's is empty (they're adjacent)
• Update: ans = max(-1, 0) = 0

i=4, c='a':

• 'a' is in dictionary at position 1!
• Calculate substring length: 4 - 1 - 1 = 2
• The substring between positions 1 and 4 is "bb" (length 2)
• Update: ans = max(0, 2) = 2

i=5, c='c':

• 'c' is in dictionary at position 0!
• Calculate substring length: 5 - 0 - 1 = 4
• The substring between positions 0 and 5 is "abba" (length 4)
• Update: ans = max(2, 4) = 4

Final Result: Return 4

The longest substring between two equal characters is "abba" (between the two 'c' characters at positions 0 and 5).

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the length of the string s. The algorithm iterates through the string exactly once using a single for loop. Each operation inside the loop (checking if a character exists in the dictionary, updating the dictionary, and calculating the maximum) takes O(1) time on average for dictionary operations.

Space Complexity: O(min(n, 26)) which simplifies to O(1) for practical purposes since we're dealing with lowercase English letters. The dictionary d stores at most one entry per unique character in the string. In the worst case where all characters are unique, the dictionary would store n entries, but since we're typically dealing with English alphabet characters, the maximum number of entries is bounded by 26 (or 52 if considering both cases, or 128/256 for extended ASCII). Therefore, the space complexity is O(1) constant space when considering the character set is fixed.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Updating the First Occurrence Position

A common mistake is updating the dictionary for every occurrence of a character, not just the first one:

Incorrect approach:

for index, char in enumerate(s):
    if char in first_occurrence:
        current_length = index - first_occurrence[char] - 1
        max_length = max(max_length, current_length)
    first_occurrence[char] = index  # Wrong: This updates for every occurrence!

Why this is wrong: By updating the position on every occurrence, you lose track of the first position, which gives you the maximum possible distance. For example, with "abcba", the two 'b's are at positions 1 and 3, giving length 1. But if you update the position, you might miss the maximum distance between the two 'a's at positions 0 and 4, which gives length 3.

Correct approach:

for index, char in enumerate(s):
    if char in first_occurrence:
        current_length = index - first_occurrence[char] - 1
        max_length = max(max_length, current_length)
    else:
        first_occurrence[char] = index  # Only store the FIRST occurrence

2. Forgetting to Subtract 1

Another pitfall is calculating the distance incorrectly by forgetting to exclude the characters themselves:

Incorrect calculation:

current_length = index - first_occurrence[char]  # Wrong: includes both characters

Why this is wrong: The problem asks for the substring between the two equal characters, excluding them. If you don't subtract 1, you're counting one of the boundary characters.

Example: For "aa" at positions 0 and 1:

• Wrong: 1 - 0 = 1 (incorrectly suggests there's 1 character between them)
• Correct: 1 - 0 - 1 = 0 (correctly shows nothing between them)

3. Not Handling the No-Repeat Case

Failing to initialize the return value to -1:

Incorrect initialization:

max_length = 0  # Wrong: assumes at least one pair exists

Why this is wrong: If no character repeats (like in "abcd"), the function should return -1, not 0. Starting with 0 would incorrectly suggest there's a valid substring of length 0.

Correct initialization:

max_length = -1  # Correct: handles the case when no character repeats