Largest Substring Between Two Equal Characters — Easy Problem & Solution

Given a string s, return the length of the longest substring that sits strictly between two equal characters, not counting those two characters themselves.

Difficulty: Easy
Topics: Strings, Hash Table
Asked at: Amazon, TCS, Infosys
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given a string s, return the length of the longest substring that sits strictly between two equal characters, not counting those two characters themselves.

If no character repeats, return -1.

Example 1

Input: s = "codekairo"
Output: 6
Explanation: The only repeated character is o, at indices 1 and 8, enclosing "dekair".

Example 2

Input: s = "abca"
Output: 2
Explanation: The two a's enclose "bc".

Example 3

Input: s = "cbzxy"
Output: -1
Explanation: Nothing repeats.

Constraints

1 <= s.length <= 300
s consists of lowercase English letters.

How to solve Largest Substring Between Two Equal Characters

The gap for a character is maximised by its earliest and latest occurrence, so storing each character's first index and measuring from it on every repeat covers every candidate.

Approach

Sweep i over s, keeping a map from character to its first index.
On a character already in the map, the candidate length is i - first[c] - 1.
Keep the maximum, starting from -1 so a string with no repeat answers correctly.

Why it works

For a character c appearing at indices i1 < i2 < … < ik, every pair gives ij - ii - 1, which is largest when ii is the first and ij the last. Measuring every occurrence against the stored first index therefore reaches that maximum.

Complexity

Time — O(n)
Space — O(1) — at most 26 entries

Pitfalls

Overwriting the stored index on each sighting measures against the previous occurrence, not the first.
Returning last - first counts the two bookend characters, which the statement excludes.

Reference solution

Python

def maxLengthBetweenEqualCharacters(s: str) -> int:
    first = {}
    best = -1
    for i, c in enumerate(s):
        if c not in first:
            first[c] = i
        elif i - first[c] - 1 > best:
            best = i - first[c] - 1
    return best

JavaScript

var maxLengthBetweenEqualCharacters = function(s) {
    var first = {}, best = -1;
    for (var i = 0; i < s.length; i++) {
        var c = s.charAt(i);
        if (first[c] === undefined) first[c] = i;
        else if (i - first[c] - 1 > best) best = i - first[c] - 1;
    }
    return best;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 282 strings problems · the whole catalogue