Largest Substring Between Two Equal Characters — LeetCode 1624 Python Solution

The problem

Given a string s, return the length of the longest substring between two equal characters, excluding the two characters. If there is no such substring return -1.

Example

Input

s = "aa"

Output

0

Explanation

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

Python solution

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

Complexity

Pattern: Hash Map

Trade memory for time: remember what you have seen so the second pass never happens. LeetCode 1624. Largest Substring Between Two Equal Characters is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Hash Table.

The hash map guide has the Python template for the pattern and the 709 LeetCode problems that use it.

Related problems