Problem 1624

Question statement

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

Solution

Main idea:

The straightforward approach is to create a dictionary that documents every distinct letter that appears in $\texttt{s}$ along with the first and last indices of its occurence in $\texttt{s}$. Now simply go through the dictionary and hunt for the letter that captures the largest interval between its first and last occurrences. If no letter is ever repeated (i.e, $\texttt{len(dict) == len(s)}$), then return $-1$.

Code:

def maxLengthBetweenEqualCharacters(self, s: str) -> int:
    dic = {}
    for i in range(len(s)):
        if s[i] not in dic:
            dic[s[i]] = [i, i]
        if s[i] in dic:
            dic[s[i]][1] = i
    if(len(dic) == len(s)):
        return -1
    
    max_len = 0
    for i in dic:
        max_len = max(max_len, (dic[i][1] - dic[i][0] - 1))
    return max_len

Comments:

Time complexity: O($\texttt{len(s)}$).

At the time of submission, the above solution passes leetcode submission cases in 35ms, beating 84.63% of users. It uses 17.38MB of memory, beating 5.46% of users.