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.

#1624

Easy

auto_awesome哈希·表·结合·string

LeetCode 题解工作台

两个相同字符之间的最长子字符串

给你一个字符串 s ，请你返回两个相同字符之间的最长子字符串的长度，计算长度时不含这两个字符。如果不存在这样的子字符串，返回 -1 。子字符串是字符串中的一个连续字符序列。示例 1：输入： s = "aa" 输出： 0 解释：最优的子字符串是两个 'a' 之间的空子字符串。示例 2…

哈希表字符串

题目描述

给你一个字符串 s，请你返回 两个相同字符之间的最长子字符串的长度 ，计算长度时不含这两个字符。如果不存在这样的子字符串，返回 -1 。

子字符串 是字符串中的一个连续字符序列。

示例 1：

输入：s = "aa"
输出：0
解释：最优的子字符串是两个 'a' 之间的空子字符串。

示例 2：

输入：s = "abca"
输出：2
解释：最优的子字符串是 "bc" 。

示例 3：

输入：s = "cbzxy"
输出：-1
解释：s 中不存在出现出现两次的字符，所以返回 -1 。

示例 4：

输入：s = "cabbac"
输出：4
解释：最优的子字符串是 "abba" ，其他的非最优解包括 "bb" 和 "" 。

提示：

1 <= s.length <= 300
s 只含小写英文字母

lightbulb

解题思路

方法一：数组或哈希表

用数组或哈希表记录字符串 $s$ 每个字符第一次出现的位置。由于本题中字符串 $s$ 只含小写英文字母，因此可以用一个长度为 $26$ 的数组 $d$ 来记录，初始时数组元素值均为 $-1$ 。

遍历字符串 $s$ 中每个字符 $c$ ，若 $c$ 在数组中的值为 $-1$ ，则更新为当前位置 $i$ ；否则我们将答案更新为当前位置 $i$ 与数组中的值 $d[c]$ 的差值的最大值减一，即 $ans = \max (ans, i - d[c]-1)$ 。

时间复杂度 $O(n)$ ，空间复杂度 $O(C)$ 。其中 $n$ 为字符串长度，而 $C$ 为字符串 $s$ 的字符集大小，本题 $C=26$ 。

1

2

3

4

5

6

7

8

9

10

11

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

speed

复杂度分析

指标	值
时间	O(n)
空间	O(1)

psychology

面试官常问的追问

外企场景

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

warning

常见陷阱

外企场景

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

swap_horiz

进阶变体

外企场景

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

help

常见问题

外企场景

继续练习

#1638 统计只差一个字符的子串数目 #1604 警告一小时内使用相同员工卡大于等于三次的人 #1647 字符频次唯一的最小删除次数