最长不含重复字符的子字符串

[编程题]最长不含重复字符的子字符串

热度指数：47997 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

数据范围:

$\ \text{s.length}\le 40000$

示例1

输入

"abcabcbb"

输出

说明

因为无重复字符的最长子串是"abc"，所以其长度为 3。

示例2

输入

"bbbbb"

输出

说明

因为无重复字符的最长子串是"b"，所以其长度为 1。

示例3

输入

"pwwkew"

输出

说明

因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是子串的长度，"pwke" 是一个子序列，不是子串。

算法知识视频讲解

矮肥

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param s string字符串
 * @return int整型
 */
func lengthOfLongestSubstring(s string) int {
	// write code here
	var char2Index = make(map[int32]int, len(s))
	var maxSub = 0
	var currentSubLen = 0

	var getMax = func(a, b int) int {
		if a > b {
			return a
		}
		return b
	}
	var left int
	for index, char := range s {
		if charIdx, exist := char2Index[char]; exist {
			if charIdx < left {
				currentSubLen += 1
			} else {
				maxSub = getMax(currentSubLen, maxSub)
				currentSubLen = index - charIdx
				left = charIdx + 1
			}
		} else {
			currentSubLen += 1
		}
		char2Index[char] = index
	}
	maxSub = getMax(currentSubLen, maxSub)
	return maxSub
}

编辑于 2024-04-21 16:46:53 回复(0)

小谷围做题家

package main
import _"fmt"

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param s string字符串 
 * @return int整型
*/
func lengthOfLongestSubstring( s string ) int {
    cnt:=map[byte]bool{}
    var l,r int
    for i,ch:=range []byte(s){
        if _,ok:=cnt[ch];!ok{
            cnt[ch]=true
        }else{
            r=i
            break
        }
    }
    max:=len(cnt)
    for ;r<len(s);r++{
        for{
            if _,ok:=cnt[s[r]];ok{
                delete(cnt,s[l])
                l++
            }else{
                break
            }
        }
        cnt[s[r]]=true
        if len(cnt)>max{
            max=len(cnt)
        }
    }
    return max
}

发表于 2023-03-04 11:07:21 回复(0)