💬 Discord
Sign In
NeetCode #80LC-1624EasyArrays & Hashing
← Back to All Problems

#80 · #1624 · Largest Substring Between Two Equal Characters(两个相同字符之间的最长子字符串)

📌 Problem Statement & Constraints

Given a string s, return the length of the longest substring between two equal characters, excluding the two characters themselves. If no such substring exists, return -1. Constraints: 1 <= s.length <= 300, lowercase letters.

💡 Core Algorithmic Approaches

  1. Only the first and last occurrence of a character can maximise the distance, so record the first occurrence of each character.
  2. Scan left to right; when a character is seen again, the gap between the two occurrences is i - first[ch] - 1.
  3. Take the maximum such gap.
  4. Record the first occurrence only the first time, otherwise later occurrences would shrink the gap.

💻 Benchmark Python3 Implementation

class Solution:
    def maxLengthBetweenEqualCharacters(self, s: str) -> int:
        first = {}
        best = -1
        for i, ch in enumerate(s):
            if ch in first:
                best = max(best, i - first[ch] - 1)   # exclude both endpoints
            else:
                first[ch] = i
        return best

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one pass.
💾 Space Complexity
O(k) for the first-occurrence map, k <= 26.

⚠️ Interview Pitfalls & Follow-ups

  • Overwriting first[ch] on every occurrence: the gap would collapse; only the first occurrence must be stored.
  • Forgetting to subtract 1: the characters between the endpoints are i - first[ch] - 1.
  • Returning 0 when no pair exists: the answer must be -1, and 0 is a legitimate answer for adjacent equal characters like "aa".