最长子串是什么

题目:
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

1
2
3
4
5
eg: 
    输入: s = "abcabcbb"
    输出: 3 
    解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

最长子串能解决什么问题?

最长子串这种问题在计算机科学和编程中有很多引用场景. 找到一个 字符串 中的最长无重复子串可以有以下应用场景:

* 文本分析以及搜索功能

在搜索引擎和数据库搜索中, 最长子串可以用来帮助我们找到最长的匹配字符串, 从而提高搜索效率和搜索精度

* 密码验证

可以用最长子串的概念来要求用户创建的密码必须包含一定长度的无重复字符串序列, 用来保证密码的复杂性和安全性

* 软件开发

在开发编程语言和工具时，最长子串问题可以用于语法高亮显示、自动补全、错误检测等功能。例如，语法高亮显示可能需要找到最长的匹配关键字，自动补全可能需要找到最长的匹配字符串，错误检测可能需要找到最长的不符合语法规则的字符串。

* 数据压缩

数据压缩中，最长子串问题可以用于查找重复的数据段，以减小文件大小。例如，LZ77（Lempel-Ziv 77）算法就是一种利用最长子串来实现数据压缩的方法。

* 文本处理

在处理大量文本数据时，诸如网络爬虫或者其他数据分析任务，寻找最长子串可以帮助我们找到最大的匹配模式，进行高效的数据提取或者清洗。

算法代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
  def lengthOfLongestSubstring(self, s: str) -> int:
      # 使用一个字典来存储每个字符的最后一次出现的位置
      last_seen = {}
      # 初始化子字符串的起始位置
      start_substring = 0
      # 初始化最大长度
      max_length = 0

      for i in range(len(s)):
          # 如果字符已经出现过，并且它的索引大于等于子字符串的起始位置
          if s[i] in last_seen and start_substring <= last_seen[s[i]]:
              # 将子字符串的起始位置移到字符最后一次出现的位置的右边
              start_substring = last_seen[s[i]] + 1
          else:
              # 更新最大长度
              max_length = max(max_length, i - start_substring + 1)
              
          # 更新字符最后一次出现的位置
          last_seen[s[i]] = i

      return max_length

这个函数采用了滑动窗口的方法，其中它跟踪子字符串的起始位置 (start_substring) 和当前位置 (i)。 它还使用一个字典 (last_seen) 来存储每个字符的最后一次出现。

对于字符串中的每个字符，它检查是否已经见过该字符，如果它在当前子字符串 (从 start_substring 到 i) 中。如果是这样，它会更新子字符串的起始位置，移到字符最后一次出现的位置的右边。否则，它会更新不含重复字符的子字符串的最大长度。

最后，它会更新当前字符的最后一次出现的位置，并继续下一个字符。

这个算法的时间复杂度是 O(n)，其中 n 是字符串的长度，因为它只扫描一次字符串。它使用 O(min(n, m)) 的空间，其中 m 是字符集的大小，因为它在字典中存储每个字符的最后一次出现。

这个算法可以用于需要找到不含重复字符的最长子字符串的各种情境，比如文本处理或字符串操作任务。

例如，要找出字符串 “abcabcbb” 中不含重复字符的最长子字符串的长度，可以如下调用函数：

1
2
print(lengthOfLongestSubstring("abcabcbb"))  # 输出：3