3.无重复字符的最长子串

3 无重复字符的最长子串

最近好久没有更新文章了,就更新一篇 LeetCode 的一篇算法的题目.

题目描述

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

示例 1:

输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

示例 2:

输入: “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。

示例 3:

输入: “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。

思路分析:

遍历字符串

定义一个变量 要求 从 start 到 x-1 位置都是 不重复的字串
要定义一个字典 记录 字符与字符上一次出现的位置的映射.

保证 从 start 到 x-1 这段数据 都是 不重复的.

定义一个 字典 last_occured, 记录 关系: 记录 字符与所在位置index 的对应关系

1. 如果 新访问的 X ,不在 laste_occured 里面 ,这说明从来没有出现过,
   或者 last_occured[X] 的index 的下标在start 之前 这里说明 这个X 可以加入到 这个start–> j-1 这个长度里面.

如果新访问的X 在 last_occured 里面 , new_index= last_occred[X] 并且下标在 start 之后 出现, 那么说明从 start 到 j-1 的闭区间里面出现过该值.
需要 更新 start 的位置, 使其满足 从start -->j-1 位置 是没有重复的字串. start 要更新到 new_index+1 的位置 .

比如这种情况

此时就要更新 start 的值,更新 start = last_occured[X]+1 的位置

图片3

1. 更新 当前 访问的 index-start +1 是否大于 max_length 如果大于 则进行更新,否则不进行更新.
2. 更新 last_occred 字典. 把字符 和对应的index 信息保存下来.

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
""" @Time : 2019/6/17 14:12 @File : length_of_none_repeat_string.py @Author : frank.chang@shoufuyou.com refer : https://blog.csdn.net/tuobicui6522/article/details/80099897 题目地址: 3. 无重复字符的最长子串 https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/ """


def max_length_of_no_repeat_substring(s: str) -> int:
    # 记录出现字符 与 index 的映射
    last_occured = dict()

    start = 0
    max_length = 0

    for i, char in enumerate(s):
        last_index = last_occured.get(char)
        if last_index is not None and last_index >= start:
            start = last_index + 1

        if i - start + 1 > max_length:
            max_length = i - start + 1

        last_occured[char] = i
    return max_length


if __name__ == '__main__':
    print(max_length_of_no_repeat_substring("abcabcbb"))  # 3

    print(max_length_of_no_repeat_substring("bbbbb")) # 1 
    print(max_length_of_no_repeat_substring("pwfwkew"))# 4
    print(max_length_of_no_repeat_substring("")) # 0
    print(max_length_of_no_repeat_substring("a")) # 1
    print(max_length_of_no_repeat_substring("abcdef"))# 6
    pass
    

最近在学习go 语言,所以下面也给是go 语言的实现版本

下面用go 语言实现一下:

package main

import "fmt"

/* https://blog.csdn.net/tuobicui6522/article/details/80099897 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。 示例 1: 输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。 示例 2: 输入: "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。 示例 3: 输入: "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。 */

func lengthOfNonRepeatingSubStr(s string) int {

	lastOccurred := make(map[rune]int) //记录字符最后出现的位置
	start := 0
	maxLength := 0

	for i, ch := range []rune(s) {

		// 遍历字符串
		if lastI, ok := lastOccurred[ch]; ok && lastI >= start {
			start = lastI + 1
		}
		if i-start+1 > maxLength {
			maxLength = i - start + 1
		}
		lastOccurred[ch] = i
	}

	return maxLength
}

func main() {

	//s := "abcdaddbcbb"

	fmt.Println(
		lengthOfNonRepeatingSubStr("abcabcbb"))
	fmt.Println(
		lengthOfNonRepeatingSubStr("bbbbb"))
	fmt.Println(
		lengthOfNonRepeatingSubStr("pwwkew"))
	fmt.Println(
		lengthOfNonRepeatingSubStr(""))
	fmt.Println(
		lengthOfNonRepeatingSubStr("b"))
	fmt.Println(
		lengthOfNonRepeatingSubStr("abcdef"))
	fmt.Println(
		lengthOfNonRepeatingSubStr("一二三二一"))

}

参考文档

go语言实现–寻找最长不含有重复字符的子串 https://blog.csdn.net/tuobicui6522/article/details/80099897