3. Longest Substring Without Repeating Characters
Leetcode 问题: 3. Longest Substring Without Repeating Characters
题目
Given a string s, find the length of the longest substring without repeating characters.
传入 字串变数 ，找出 最长的子字串字元 长度
答案
Golang
1. 解法1 使用 bit
func lengthOfLongestSubstring1(check_text string) int {
// 被检查的文字长度
check_text_length := len(check_text)
if check_text_length == 0 {
// 验证字串长度为 0 不检查
return 0
}
// 文字 ASCII 检查设定，预设都没有找到此文字 false
var text_ascii_bit_set [256]bool
// 右方指标字元 ASCII Code
var right_character_ascii_code uint8
// 左方指标字元 ASCII Code
var left_character_ascii_code uint8
// 左方字元索引
left_character_index := 0
// 右方字元索引
right_character_index := 0
// 检查文字最大不重複字串长度
check_text_longest_string_length := 0
// 目前字串长度
current_text_string_length := 0
for left_character_index < check_text_length {
// 左侧字元索引小于检查字串长度，还没有全部检查完，继续检查
// 右方指标字元 ASCII Code
right_character_ascii_code = check_text[right_character_index]
// 左方指标字元 ASCII Code
left_character_ascii_code = check_text[left_character_index]
if text_ascii_bit_set[right_character_ascii_code] {
// 若右方文字已经有出现过，表示从左方索引到右方索引中间已经有出现过该文字
// 左方文字设定为未出现过 false
text_ascii_bit_set[left_character_ascii_code] = false
// 左方往右推进 1 个字元，继续检查搜寻
left_character_index++
} else {
// 右方文字没有出现过，设定右方文字为已出现过 true
text_ascii_bit_set[right_character_ascii_code] = true
// 右方指标往前搜寻
right_character_index++
}
// 设定目前字串长度
current_text_string_length = right_character_index - left_character_index
if check_text_longest_string_length < current_text_string_length {
// 若右方指标在左方指标前面，且长度大于目前检查文字的最大长度，将目前长度设定为最大长度
check_text_longest_string_length = current_text_string_length
}
if left_character_index+check_text_longest_string_length >= check_text_length || right_character_index >= check_text_length {
// 1. 左方字元索引 + 目前检查文字的最大长度 > 文字最大长度：再往右找也找不到更长的文字了
// 2. 右方字元索引 >= 被检查的文字长度 : 已经检查到最后一个字元了
// 跳出检查
break
}
}
return check_text_longest_string_length
}
2. 解法2 使用 sliding window
func lengthOfLongestSubstring(check_text string) int {
// 被检查的文字长度
check_text_length := len(check_text)
if check_text_length == 0 {
// 验证字串长度为 0 不检查
return 0
}
// 建立长度 256 的整数阵列
var text_ascii_int_flag [256]int
// 左方字元索引
left_character_index := 0
// 右方字元索引
right_character_index := 0
// 检查文字最大不重複字串长度
check_text_longest_string_length := 0
// 右方指标字元 ASCII Code
var right_character_ascii_code uint8
// 左方指标字元 ASCII Code
var left_character_ascii_code uint8
// 目前字串长度
current_text_string_length := 0
for left_character_index < check_text_length {
// 若左侧指标小于字串长度，继续检查
if right_character_index >= check_text_length {
// 若右侧指标大于字串长度，表示已经检查到最后的字串了，不需要再检查
break
}
// 右方指标字元 ASCII Code
right_character_ascii_code = check_text[right_character_index]
if text_ascii_int_flag[right_character_ascii_code] == 0 {
// 「右侧指标 +1 小于字串长度，表示字串还没全部检查完」且「此文字未出现过」
// 标记右方文字出现过
text_ascii_int_flag[right_character_ascii_code] = 1
// 继续往右检查
right_character_index++
} else {
// 左方指标字元 ASCII Code
left_character_ascii_code = check_text[left_character_index]
// 标记左方文字没出现过
text_ascii_int_flag[left_character_ascii_code] = 0
// 将左方指标往前移动
left_character_index++
}
// 设定目前字串长度
current_text_string_length = right_character_index - left_character_index
if check_text_longest_string_length < current_text_string_length {
// 若右方指标在左方指标前面，且长度大于目前检查文字的最大长度，将目前长度设定为最大长度
check_text_longest_string_length = current_text_string_length
}
}
return check_text_longest_string_length
}
Python
class Solution:
def lengthOfLongestSubstring(self, check_text: str) -> int:
# 被检查的文字长度
check_text_length = len(check_text)
# 验证字串长度为 0 不检查
if check_text_length == 0:
return 0
# 建立长度 256 的整数字典
text_ascii_int_flag = {}
# 左方字元索引
left_character_index: int = 0
# 右方字元索引
right_character_index: int = 0
# 检查文字最大不重複字串长度
check_text_longest_string_length: int = 0
# 右方指标字元 ASCII Code
right_character_ascii_code: int = 0
# 左方指标字元 ASCII Code
left_character_ascii_code: int = 0
# 目前字串长度
current_text_string_length: int = 0
while left_character_index <= check_text_length:
# 若左侧指标小于字串长度，继续检查
if right_character_index >= check_text_length:
# 若右侧指标大于字串长度，表示已经检查到最后的字串了，不需要再检查
break
# 右方指标字元 ASCII Code
right_character_ascii_code = ord(check_text[right_character_index])
if right_character_ascii_code not in text_ascii_int_flag:
# 「右侧指标 + 1 小于字串长度，表示字串还没全部检查完」且「此文字未出现过」
# 标记右方文字出现过
text_ascii_int_flag[right_character_ascii_code] = 1
# 继续往右检查
right_character_index += 1
else:
# 左方指标字元 ASCII Code
left_character_ascii_code = ord(check_text[left_character_index])
# 删除标记左方文字没出现过
del text_ascii_int_flag[left_character_ascii_code]
# 将左方指标往前移动
left_character_index += 1
# 设定目前字串长度
current_text_string_length = right_character_index - left_character_index
if check_text_longest_string_length < current_text_string_length:
# 若右方指标在左方指标前面，且长度大于目前检查文字的最大长度，将目前长度设定为最大长度
check_text_longest_string_length = current_text_string_length
if left_character_index + check_text_longest_string_length >= check_text_length or right_character_index >= check_text_length:
# 1. 左方字元索引 + 目前检查文字的最大长度 > 文字最大长度：再往右找也找不到更长的文字了
# 2. 右方字元索引 >= 被检查的文字长度: 已经检查到最后一个字元了
# 跳出检查
break
return check_text_longest_string_length
if __name__ == '__main__':
# begin
s = Solution()
print(s.lengthOfLongestSubstring('abcabcbb'))
print(s.lengthOfLongestSubstring('bbbbb'))