难度: Medium
Submission
运行时间: 135 ms
内存: 16.4 MB
class Solution:
def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:
x0, x1, y0, y1, srt, mx = -1, -1, '#', '@', -1, 0
for i,v in enumerate(s):
if v==y0: x0 = i
elif v==y1: x1 = i
else:
if x0 > x1: x0, y0, x1, y1 = x1, y1, x0, y0
srt, x0, y0 = x0, i, v
mx = max(mx, i - srt)
return mx
Explain
该题解使用滑动窗口的思路来解决问题。通过维护两个指针 x0 和 x1 分别记录窗口内最多两个不同字符的位置，同时用 y0 和 y1 记录对应的字符。每次遇到一个新字符时，根据情况更新 x0, x1, y0, y1 以及窗口的起始位置 srt，并更新最大长度 mx。最终返回 mx 即为所求的最长子串长度。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:
x0, x1, y0, y1, srt, mx = -1, -1, '#', '@', -1, 0
for i,v in enumerate(s):
if v==y0: # 如果当前字符与y0相同，更新x0为当前位置
x0 = i
elif v==y1: # 如果当前字符与y1相同，更新x1为当前位置
x1 = i
else: # 如果当前字符与y0和y1都不同
if x0 > x1: # 如果x0大于x1，交换x0和x1，y0和y1
x0, y0, x1, y1 = x1, y1, x0, y0
srt, x0, y0 = x0, i, v # 更新窗口起始位置为x0，x0为当前位置，y0为当前字符
mx = max(mx, i - srt) # 更新最大长度为当前位置减去窗口起始位置和mx的较大值
return mx
Explore
在算法中，每次循环都会检查当前字符 v 是否等于 y0 或 y1。如果等于其中之一，例如 y0，则更新 x0 的位置为当前字符的索引，表示 y0 字符的最新位置。如果 v 不是 y0 或 y1，这意味着出现了一个新的字符，这时会判断 x0 和 x1 的大小（哪个更小，即哪个字符最早出现），并将较早的那个字符（x1）替换为新字符 v，同时更新 x0 和 y0 为当前字符的位置和值。这样，x0 和 x1 始终保留了窗口中最后出现的两个不同字符的位置。
当出现一个新的字符需要更新窗口时，通过设置 srt 为 x0 的原因是在此之前 x0 位置的字符 y0 将不再是窗口中的有效字符，而将被新字符替换。因此，窗口的新起始位置应该是 x0 之后（即 x0 的位置），这是为了确保窗口内只有最多两个不同的字符。如果设置为 x1，则可能会包括被替换的旧字符，导致窗口内包含三个不同的字符。
在算法中，y0 和 y1 用来存储当前窗口中的两个不同字符。x0 和 x1 是这两个字符最后一次出现在字符串中的位置索引。每次碰到字符串中的字符 v 时，算法会检查 v 是否与 y0 或 y1 相等。如果相等，就更新相应的位置索引 x0 或 x1。如果 v 与 y0 和 y1 都不相同，表明遇到了一个新字符，这时候会更新其中一个旧字符的位置和值（基于 x0 和 x1 的比较），以保证窗口中只有两种字符。
如果遇到的字符序列中只有一种字符，例如全部都是字符 'a'，那么每次遇到这个字符时，算法会检测到 v 是 y0 或 y1 中的一个（取决于初始或中间某状态下的赋值），并相应更新 x0 或 x1。由于没有第二种字符，x1 的值可能始终保持初始值。窗口起始位置 srt 在遇到第一个字符时被设置，后续不再改变，因为没有新的字符类型加入。因此，srt 将保持为初始索引 0，x0 或 x1 会更新为当前字符的最新位置，另一个保持不变。