Code Implementation

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

class Solution {
public:
    int maxLengthBetweenEqualCharacters(string s) {
        unordered_map<char, int> first_index;
        int max_len = -1;
        for (int i = 0; i < s.size(); ++i) {
            char ch = s[i];
            if (first_index.count(ch)) {
                max_len = max(max_len, i - first_index[ch] - 1);
            } else {
                first_index[ch] = i;
            }
        }
        return max_len;
    }
};
      

class Solution {
    public int maxLengthBetweenEqualCharacters(String s) {
        Map<Character, Integer> firstIndex = new HashMap<>();
        int maxLen = -1;
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (firstIndex.containsKey(ch)) {
                maxLen = Math.max(maxLen, i - firstIndex.get(ch) - 1);
            } else {
                firstIndex.put(ch, i);
            }
        }
        return maxLen;
    }
}
      

var maxLengthBetweenEqualCharacters = function(s) {
    let firstIndex = {};
    let maxLen = -1;
    for (let i = 0; i < s.length; i++) {
        let ch = s[i];
        if (firstIndex.hasOwnProperty(ch)) {
            maxLen = Math.max(maxLen, i - firstIndex[ch] - 1);
        } else {
            firstIndex[ch] = i;
        }
    }
    return maxLen;
};
      

Problem Description

Given a string s, find the length of the largest substring that is located between two equal characters in s. Specifically, for any two equal characters at different positions in the string, calculate the length of the substring that lies strictly between them (excluding the two characters themselves). If there are no two equal characters, return -1.

• You may assume that the input string s contains only lowercase English letters.
• There can be multiple pairs of equal characters; you must return the length of the largest such substring found.
• Characters may not be reused across different pairs; each pair is considered independently.

Thought Process

The problem asks us to find the maximum length between two equal characters in a string. At first glance, a brute-force approach might involve checking every possible pair of characters and calculating the substring length between them. However, this would be inefficient for long strings.

To optimize, we realize that for each character, the largest possible substring is found between its first and last occurrence. This is because the distance between the first and last occurrence is always greater than or equal to the distance between any other pair of identical characters. Therefore, instead of checking all pairs, we can record the first occurrence of each character and, as we iterate through the string, compare it to the current index whenever we see the same character again.

Solution Approach

• Step 1: Initialize a dictionary (or hash map) to store the first occurrence index of each character in the string.
• Step 2: Initialize a variable to keep track of the maximum length found so far, starting at -1.
• Step 3: Iterate through the string character by character, using the index and the character.
  • If the character has been seen before (exists in the dictionary), calculate the distance from the current index to its first occurrence, subtract 1 (since we want the substring between them), and update the maximum length if this is larger than the current value.
  • If the character has not been seen before, record its index as its first occurrence.
• Step 4: After the loop, return the maximum length found. If no two equal characters were found, -1 will be returned.

We use a dictionary because it allows us to look up the first occurrence of any character in constant time, making the overall algorithm efficient.

Example Walkthrough

Let's consider the input s = "abca".

1. We start with an empty dictionary and max_len = -1.
2. At index 0, character 'a': not seen before, record index 0.
3. At index 1, character 'b': not seen before, record index 1.
4. At index 2, character 'c': not seen before, record index 2.
5. At index 3, character 'a': seen before at index 0. Calculate substring length: 3 - 0 - 1 = 2. Update max_len = 2.

The answer is 2 because the largest substring between two equal characters ('a' at index 0 and 3) is "bc", which has length 2.

Time and Space Complexity

• Brute-force Approach: Checking all pairs of equal characters would require two nested loops, resulting in O(n^2) time complexity, where n is the length of the string.
• Optimized Approach (as above): We make a single pass through the string, doing constant-time operations for each character. Thus, the time complexity is O(n).
• Space Complexity: We store at most one entry for each unique character (up to 26 for lowercase letters), so space complexity is O(1) (constant).

Summary

The key insight is that the largest substring between two equal characters is always found between the first and last occurrence of that character. By keeping track of the first occurrence index for each character and updating the maximum length whenever we see a repeat, we achieve an efficient and elegant solution. This approach avoids unnecessary comparisons and leverages hash maps for quick lookups, resulting in a linear time algorithm suitable for large inputs.