Max Gap Between Two Same

Time: O(n)

Space: O(1)

Problem Overview

We need the largest number of characters strictly between two equal letters.

Intuition

We need the largest number of characters strictly between two equal letters. Scan left to right and remember the first index of each letter; when a letter repeats, the gap is current index minus first index minus one.

Algorithm

1Initialize first[26] = −1 and maxGap = −1.
2For each index i and character c: if first[c] is unset, store i; else update maxGap with i − first[c] − 1.
3Return maxGap (stays −1 if no character appears twice).

Example Walkthrough

Input: s = "acdbtxtz"

1. First "t" at index 4; second "t" at index 7.
2. Gap between them = 7 − 4 − 1 = 2 characters ("xt").

Output: 2

Common Pitfalls

• Gap counts characters between the two occurrences, not including the matching letters.
• Only the first occurrence matters for each character; later repeats compare against that first index.

Max Gap Between Two Same.java

Java

// Approach: Track the first index of each letter. On a repeat, gap = i - first - 1; keep the max.
// Time: O(n) Space: O(1)

import java.util.*;

class Solution {

    public int maxCharGap(String s) {
        int maxGap = -1;
        int[] first = new int[26];
        Arrays.fill(first, -1);
        for (int i = 0; i < s.length(); i++) {
            int idx = s.charAt(i) - 'a';
            if (first[idx] == -1) {
                first[idx] = i;
            } else {
                int currGap = i - first[idx] - 1;
                maxGap = Math.max(maxGap, currGap);
            }
        }
        return maxGap;
    }
}

Was this solution helpful?