招式拆解 I

难度: Medium

某套连招动作记作序列 arr，其中 arr[i] 为第 i 个招式的名字。请返回 arr 中最多可以出连续不重复的多少个招式。

示例 1:

输入: arr = "dbascDdad"
输出: 6
解释: 因为连续且最长的招式序列是 "dbascD" 或 "bascDd"，所以其长度为 6。

示例 2:

输入: arr = "KKK"
输出: 1
解释: 因为无重复字符的最长子串是 "K"，所以其长度为 1。

示例 3:

输入: arr = "pwwkew"
输出: 3
解释: 因为连续且最长的招式序列是 "wke"，所以其长度为 3。     
请注意区分 子串 与 子序列 的概念：你的答案必须是 连续招式 的长度，也就是 子串。而 "pwke" 是一个非连续的 子序列，不是 子串。

提示：

0 <= arr.length <= 40000
arr 由英文字母、数字、符号和空格组成。

注意：本题与主站 3 题相同：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

Submission

运行时间: 1868 ms

内存: 15 MB

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if len(s) == 0:
            return 0
        record = dict()
        max_length = 1
        cur_length = 0
        ind = 0
        while ind < len(s):
            char = s[ind]
            if char in record:
                max_length = max(ind - record[char], max_length)
                ind = record[char] + 1
                cur_length = 0
                record.clear()
                continue
            record[char] = ind
            print(char)
            cur_length += 1
            max_length = max(cur_length, max_length)
            ind += 1
        return max_length


if __name__ == '__main__':
    s = Solution()
    print(s.lengthOfLongestSubstring("dvdf"))

Explain

本题解采用了滑动窗口的方法来寻找最长的无重复字符的子串。使用一个字典 record 来记录字符最近一次出现的位置。遍历字符串，对于每个字符，首先检查它是否在 record 中已存在。如果存在，说明当前字符重复，此时更新 max_length 并调整窗口的起始位置到重复字符的下一个位置，并重置当前长度和字典。如果不存在，将字符及其索引加入 record，并更新当前长度和最大长度。这种方式确保了每当遇到重复字符时，窗口能够适当地移动到重复字符的下一位，从而继续寻找可能的更长的无重复子串。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if len(s) == 0:
            return 0  # 空字符串直接返回 0
        record = dict()  # 记录字符最近一次出现的位置
        max_length = 1  # 初始化最大长度为 1
        cur_length = 0  # 当前窗口长度
        ind = 0  # 初始化索引位置
        while ind < len(s):
            char = s[ind]  # 当前字符
            if char in record:
                max_length = max(ind - record[char], max_length)  # 更新最大长度
                ind = record[char] + 1  # 重置窗口起始位置
                cur_length = 0  # 重置当前长度
                record.clear()  # 清空记录
                continue
            record[char] = ind  # 记录当前字符的索引
            cur_length += 1  # 窗口长度增加
            max_length = max(cur_length, max_length)  # 更新最大长度
            ind += 1
        return max_length

Explore

重置窗口到重复字符的下一个位置是为了确保窗口内的子串不包含重复字符，从而维持子串的有效性。这种方法有效地避免了重复字符带来的干扰，并允许算法继续探索随后的可能的更长无重复子串。这种处理方式在大多数情况下是有效的，因为它直接跳过了所有已知的重复字符，有效减少了不必要的重复检查。然而，这也意味着每次遇到重复字符时，窗口的大小和内容都会进行较大调整，可能会导致一些复杂度上的增加，尤其是在字符串包含许多重复字符时。

使用字典`record`来存储字符索引是一种常见且有效的方法，因为它提供了常数时间的查找、插入和删除操作。对于大部分情况，这是滑动窗口算法中非常高效的数据结构。尽管如此，如果字符集非常有限（例如ASCII字符集），使用固定大小的数组来代替字典可能会更有效率，因为这可以通过直接索引来访问元素，而不是通过哈希映射。此外，数组通常在内存使用和访问速度方面比字典更优。

在算法中，使用`max(ind - record[char], max_length)`更新最大长度是为了确保无论何时发现重复字符，都能正确计算并更新当前无重复子串的长度。这种方法考虑到了从当前重复字符的上一个位置到当前位置的距离，这是因为它提供了当前考虑的子串的实际长度。如果仅使用当前长度来更新，可能会忽略之前的重复字符对窗口大小的影响。因此，这种方法确保了长度计算的准确性和算法的正确性。

对于空字符串直接返回0是一种有效的处理方式，因为空字符串不包含任何字符，因此其最长无重复子串的长度自然为0。这种处理方法简单且直接，对于算法的其余部分没有影响，因此不需要进一步优化。在很多算法实现中，处理边界情况（如空输入）通常是必要的，以避免在运行时产生错误或不合适的行为。