Largest Substring Between Two Equal Characters

Easy
629.

Largest Substring Between Two Equal Characters

Largest Substring Between Two Equal Characters is an easy coding problem on strings and hash table, asked in Amazon, TCS and Infosys interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {number}
 */
var maxLengthBetweenEqualCharacters = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Largest Substring Between Two Equal Characters — Solution

Largest Substring Between Two Equal Characters solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Largest Substring Between Two Equal Characters is an easy coding problem on strings and hash table, asked in Amazon, TCS and Infosys interviews.

  • 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.

Hints for Largest Substring Between Two Equal Characters

  1. Hint 1

    For a fixed character, the widest gap always uses its first and last occurrence.

  2. Hint 2

    So record the first index of each character and, on every later sighting, measure back to it.

  3. Hint 3

    The answer counts the characters strictly inside, which is last - first - 1.

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

  1. Sweep i over s, keeping a map from character to its first index.
  2. On a character already in the map, the candidate length is i - first[c] - 1.
  3. 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

Java

public static 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] < 0) first[c] = i;
        else if (i - first[c] - 1 > best) best = i - first[c] - 1;
    }
    return best;
}

C++

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] < 0) first[c] = i;
        else if (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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Hashing: Hash Maps and Hash Sets