Largest Substring Between Two Equal Characters

easy string hash map

Problem

Given a string s, return the length of the longest substring between two equal characters, excluding the two characters themselves. If there is no such pair, return -1.

Inputs = "abca"

Output2

The two 'a's enclose "bc", which has length 2.

def max_length_between_equal_characters(s):
    first = {}
    best = -1
    for i, ch in enumerate(s):
        if ch in first:
            best = max(best, i - first[ch] - 1)
        else:
            first[ch] = i
    return best

function maxLengthBetweenEqualCharacters(s) {
  const first = {};
  let best = -1;
  for (let i = 0; i < s.length; i++) {
    const ch = s[i];
    if (ch in first) {
      best = Math.max(best, i - first[ch] - 1);
    } else {
      first[ch] = i;
    }
  }
  return best;
}

class Solution {
    public int maxLengthBetweenEqualCharacters(String s) {
        int[] first = new int[26];
        Arrays.fill(first, -1);
        int best = -1;
        for (int i = 0; i < s.length(); i++) {
            int c = s.charAt(i) - 'a';
            if (first[c] == -1) first[c] = i;
            else best = Math.max(best, i - first[c] - 1);
        }
        return best;
    }
}

int maxLengthBetweenEqualCharacters(string s) {
    vector<int> first(26, -1);
    int best = -1;
    for (int i = 0; i < (int)s.size(); i++) {
        int c = s[i] - 'a';
        if (first[c] == -1) first[c] = i;
        else best = max(best, i - first[c] - 1);
    }
    return best;
}

Explanation

For any character that repeats, the widest gap it can enclose is between its very first appearance and its very last one. So we only ever need to remember where each character first showed up.

We keep a map first from character to the index where we first saw it. As we scan, the first time we meet a character we just record its index and move on.

The next time we see the same character at index i, the substring strictly between them has length i - first[ch] - 1 (we subtract 1 to exclude the two matching characters). We compare that against the running best.

Because first[ch] always holds the earliest index, every later repeat is automatically measured against the leftmost twin — that is the largest possible span for that character, so a single pass suffices. If nothing ever repeats, best stays at its initial -1.

Example: "abca". We record a@0, b@1, c@2. At index 3 we meet a again: gap = 3 − 0 − 1 = 2, so the answer is 2.

Time: O(n) Space: O(1)