#1624

Easy

LeetCode Problem Workspace

Largest Substring Between Two Equal Characters

Find the longest substring between two equal characters using a hash table for optimized performance.

Problem Statement

Given a string s, you need to return the length of the longest substring between two equal characters, excluding the two characters. If no such substring exists, return -1.

A substring is defined as a contiguous sequence of characters within a string. For example, if the string is 'abca', the longest valid substring between equal characters is 'bc'.

Examples

Example 1

Input: s = "aa"

Output: 0

The optimal substring here is an empty substring between the two 'a's.

Example 2

Input: s = "abca"

Output: 2

The optimal substring here is "bc".

Example 3

Input: s = "cbzxy"

Output: -1

There are no characters that appear twice in s.

Constraints

1 <= s.length <= 300
s contains only lowercase English letters.

Solution Approach

Use a Hash Table to Track Character Positions

Iterate through the string, and for each character, check if it has appeared before. If it has, calculate the substring's length by subtracting the first occurrence from the current index, and keep track of the maximum length found. If it hasn't appeared before, store its index in the hash table.

Check for Edge Case: No Repeated Characters

If there are no repeated characters in the string, immediately return -1. This can be determined during the iteration by checking the hash table for the first appearance of each character.

Handle Small Strings Efficiently

For strings with a length of 1 or 2, the answer is straightforward. Return 0 if the two characters are the same, and -1 if they are different.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

The time complexity of the solution is O(n) since we iterate over the string once. The space complexity is O(1) because the size of the hash table is limited to 26 entries (one for each lowercase English letter).

What Interviewers Usually Probe

Candidate should demonstrate understanding of hash table usage in strings.
The candidate should be able to quickly identify when no solution exists.
A solid candidate would optimize the process by eliminating unnecessary calculations.

Common Pitfalls or Variants

Common pitfalls

Forgetting to exclude the two equal characters when calculating the substring length.
Over-complicating the problem by using unnecessary data structures or algorithms.
Failing to handle edge cases like strings of length 1 or strings with no repeated characters.

Follow-up variants

What if the string contains uppercase letters? How would you handle it?
How would this solution scale if the string is a very large dataset (e.g., millions of characters)?
What if the problem required finding the longest substring between two equal characters of different types (e.g., digits or symbols)?

FAQ

What is the main algorithmic approach for solving Largest Substring Between Two Equal Characters?

The main approach uses a hash table to store the first occurrence of each character, allowing you to calculate the longest substring between equal characters in O(n) time.

Why does the solution to Largest Substring Between Two Equal Characters have O(n) time complexity?

The algorithm only iterates through the string once, and each operation within the loop (checking the hash table, updating the maximum length) takes constant time, resulting in O(n) time complexity.

What should you do if there are no equal characters in the string?

In this case, the solution should immediately return -1, as there is no valid substring between two equal characters.

What is the space complexity of the solution for Largest Substring Between Two Equal Characters?

The space complexity is O(1) because the size of the hash table is constant, limited to the number of distinct lowercase English letters (26).

Can the solution to Largest Substring Between Two Equal Characters be optimized further?

No, the solution is already optimized for time complexity with O(n). Space complexity is also minimal, and there are no unnecessary operations or data structures.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

class Solution:
    def maxLengthBetweenEqualCharacters(self, s: str) -> int:
        d = {}
        ans = -1
        for i, c in enumerate(s):
            if c in d:
                ans = max(ans, i - d[c] - 1)
            else:
                d[c] = i
        return ans

Continue Practicing

#1638 count substrings that differ by one character #1604 alert using same key card three or more times in a one hour period #1647 minimum deletions to make character frequencies unique