Problem

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.

Examples

Example 1:

1
2
3

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

Example 2:

1
2
3

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

Example 3:

1
2
3

Input: s = "cbzxy"
Output: -1
Explanation: There are no characters that appear twice in s.

Solution

Method 1 - Using hashmap

To solve the problem of finding the length of the longest substring between two equal characters in the given string s, we need to consider the following points:

  1. Identifying Equal Characters:

    • We need to track the first occurrence of each character as we traverse the string.
    • For each character encountered, check if it has appeared before.

  2. Calculating the Length of Substrings:

    • If the character has appeared before, calculate the length of the substring between the first occurrence and the current position, excluding the two characters themselves.
    • Update the maximum length found so far.

  3. Return the Result:

    • If no such substrings exist, return -1. Otherwise, return the maximum length found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

public class Solution {
    public int maxLengthBetweenEqualCharacters(String s) {
        Map<Character, Integer> map = new HashMap<>();
        int ans = -1;
        
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (map.containsKey(c)) {
                ans = Math.max(ans, i - map.get(c) - 1);
            } else {
                map.put(c, i);
            }
        }
        
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

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

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the string s. This is because we traverse the string linearly once.
  • 🧺 Space complexity: O(n) for storing the first occurrence of characters since we use a fixed-size array.