Largest Substring Between Two Equal Characters

How it works

Since the input contains only lowercase letters, we can replace the hash map with a fixed-size array of 26 elements. This provides constant-time lookups and slightly better cache performance.

Steps

1. Create an array of size 26, initialized to -1 (indicating unseen characters).
2. Iterate through the string:
   • Convert the character to an index (0-25).
   • If the index has been seen (value is not -1), compute the distance and update the maximum.
   • Otherwise, store the current position as the first occurrence.
3. Return the maximum distance found.

Complexity

• Time complexity: O(n)
• Space complexity: O(1) since we have at most 26 different characters.

Things to watch for

Off-by-One in Substring Length

The substring between two equal characters at indices i and j has length j - i - 1, not j - i. Using j - i includes one of the boundary characters in the count, giving an answer that is one larger than correct.

Returning Wrong Default Value

When no two equal characters exist in the string, the answer should be -1. A common mistake is to initialize the result to 0 and forget to handle the case where no matching pair is found, incorrectly returning 0 instead of -1.

class Solution:
    def maxLengthBetweenEqualCharacters(self, s: str) -> int:
        firstIdx = [-1] * 26
        res = -1

        for i, c in enumerate(s):
            j = ord(c) - ord('a')
            if firstIdx[j] != -1:
                res = max(res, i - firstIdx[j] - 1)
            else:
                firstIdx[j] = i

        return res

class Solution {
public:
    int maxLengthBetweenEqualCharacters(string s) {
        int firstIdx[26];
        fill(begin(firstIdx), end(firstIdx), -1);
        int res = -1;

        for (int i = 0; i < s.size(); i++) {
            int j = s[i] - 'a';
            if (firstIdx[j] != -1) {
                res = max(res, i - firstIdx[j] - 1);
            } else {
                firstIdx[j] = i;
            }
        }

        return res;
    }
};