现在我来详细讲解“华为2019校招笔试题之处理字符串(python版)”的完整攻略。
标题
首先，我们需要为文章添加标题，以便读者能够快速了解文章的主题。在本文中，我们将使用以下标题：
华为2019校招笔试题之处理字符串(python版)完整攻略
题目说明
本题要求我们完成如下任务：
给定一个字符串s，求出该字符串中不包含重复字符的最长子串的长度。
分析
在解决此问题之前，我们需要完成如下两个步骤：
- 理解题目需求：题目要求我们找出不包含重复字符的最长子串长度。例如，若字符串为“abcabcbb”，则结果应为3，因为最长的不包含重复字符的子串是“abc”。
- 选择解决方案：我们可以使用暴力方法和滑动窗口法来解决此问题。由于暴力方法时间复杂度较高，我们将使用滑动窗口法来实现。
使用滑动窗口法的基本思路：
维护两个指针：left和right。分别表示不包含重复字符的子串的左右边界。
使用字典dict来维护已经遍历过的字符以及最近一次该字符出现的位置。
每次移动右指针，并判断右指针所指向的字符是否在字典dict中出现过。
如果没有出现过，则将该字符及其位置添加到字典dict中。
如果出现过，则移动左指针到该字符上次出现的位置的下一个位置，并更新该字符的位置。
在每一步操作中，记录不包含重复字符的最长子串长度。
代码实现
在Python中，实现滑动窗口算法的代码如下：
def lengthOfLongestSubstring(s: str) -> int:
left, right = 0, 0
dict = {}
res = 0
while right < len(s):
if s[right] not in dict:
dict[s[right]] = right
right += 1
res = max(res, right - left)
else:
index = dict[s[right]]
while left <= index:
del dict[s[left]]
left += 1
dict[s[right]] = right
right += 1
return res
以上代码使用了Python中的字典类型dict来维护已经遍历过的字符及其位置。在每一轮迭代中，记录窗口中不包含重复字符的最长子串长度。
示例说明
以字符串s=”abcabcbb”为例，我们来演示上述算法的执行过程。
-
初始化左边界left和右边界right均为0，字典dict为空，结果res为0。
-
当right指向第一个字符时，该字符’a’不在字典dict中，将其添加到dict中，并将right右移一位。此时，窗口中不包含重复字符，更新res为1。
-
当right指向第二个字符’b’时，该字符不在dict中，同样添加到dict中并将right右移一位。此时，窗口中不包含重复字符，更新res为2。
-
当right指向第三个字符’c’时，该字符不在dict中，同样添加到dict中并将right右移一位。此时，窗口中不包含重复字符，更新res为3。
-
当right指向第四个字符’a’时，该字符在dict中出现过，根据之前说的思路，将left移到该字符上次出现位置的下一个位置。即left移到1这个位置，将dict中’a’及其前面的字符从dict中删除，并将新的’a’及其位置添加到dict中。这时，窗口中不包含重复字符，更新res为3。
-
当right指向第五个字符’b’时，该字符在dict中出现过，同样将left移到2这个位置，并删除dict中’b’前面的字符。将新的’b’及其位置添加到dict中。这时，窗口中不包含重复字符，更新res为3。
-
当right指向第六个字符’c’时，该字符在dict中出现过，同样将left移到3这个位置，并删除dict中’c’前面的字符。将新的’c’及其位置添加到dict中。这时，窗口中包含重复字符’b’，更新res为3。
-
当right指向第七个字符’b’时，该字符在dict中出现过，同样将left移到5这个位置，并删除dict中’b’前面的字符。将新的’b’及其位置添加到dict中。这时，窗口中包含重复字符’a’和’c’，更新res为3。
-
当right指向第八个字符’b’时，该字符在dict中出现过，同样将left移到6这个位置，并删除dict中’b’前面的字符。将新的’b’及其位置添加到dict中。这时，窗口中不包含重复字符，更新res为3。
-
程序结束，返回结果3。
参考资料
本文参考了LeetCode中题目“3. Longest Substring Without Repeating Characters”的题解。