首页 > 其他分享 >3. 无重复字符的最长子串

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

时间:2024-09-02 12:23:35浏览次数:10  
标签:子串 字符 重复 maxLen mp 最长

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

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

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

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

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

提示:
0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成


滑动窗口。

也就是说从数组里面找到一个最长连续的子串从i到j里面不含相同的字符。就比如字符串“pwwkew”:pw、w、wke、kew、ew、w。

最长长度是3。使用两层循环来判断这个子串是否重复,外层循环将每个字符当做起始值开始寻找最长子串,内层循环向后寻找最长的终止字符。

func lengthOfLongestSubstring(s string) int {
	mp := make(map[byte]int)
	i, j, maxLen := 0, 0, 0
	for j < len(s) {
		// 记录当前字符
		c := s[j]
		// 向右移动窗口
		j++
		// 记录字符数量,判断是否重复
		mp[c]++
		for mp[c] > 1 {
			// 字符重复,左指针向右移,数据更新
			mp[s[i]]--
			i++
		}
		maxLen = max(maxLen, j-i)
	}
	return maxLen
}

标签:子串,字符,重复,maxLen,mp,最长
From: https://blog.csdn.net/m0_73337964/article/details/141816088

相关文章

  • 最长上升子序列
    给定一个长度为 NN 的数列,求数值严格单调递增的子序列的长度最长是多少。输入格式第一行包含整数 NN。第二行包含 NN 个整数,表示完整序列。输出格式输出一个整数,表示最大长度。数据范围1≤N≤10001≤N≤1000,−109≤数列中的数≤109−109≤数列中的数≤109输入样......
  • 我可以将 javascript 变量设置为包含 php 代码输出的字符串吗?
    在JavaScript中,你可以将一个变量设置为包含PHP代码输出的字符串。你可以使用AJAX(异步JavaScript和XML)或FetchAPI来从服务器获取PHP代码的输出,并将其存储在JavaScript变量中。以下是使用AJAX的示例代码://创建一个XMLHttpRequest对象varxhr=newXMLHttpReque......
  • File类,递归,字符集,IO流(字节流,字符流,缓冲流,转换流,转换流,序列化流,释放资源的方式)
    目录一、File类二、递归三、字符集四、IO流1.概述2.字节流3.字符流4.缓冲流5.转换流6.打印流7.数据流8.序列化流9.释放资源的方式一、File类File是java.io.包下的类,File类的对象,用于代表当前操作系统的文件(可以是文件、或文件夹)。注意:File类只能对文件本身进行操......
  • 1312. 让字符串成为回文串的最少插入次数
    1312.让字符串成为回文串的最少插入次数给你一个字符串s,每一次操作你都可以在字符串的任意位置插入任意字符。请你返回让s成为回文串的最少操作次数。「回文串」是正读和反读都相同的字符串。示例1:输入:s="zzazz"输出:0解释:字符串"zzazz"已经是回文串了,所......
  • 58集团23校招测试工程师卷——字符串处理
    Top5热词问题为了提高用户体验,后台要对用户的搜索词进行统计以方便后续做针对性的优化升级。统计策略如下:筛选出搜索词集合中的搜索次数排名前5的搜索词(不考虑搜索词数相同情况)。输入的搜索词数据格式:化妆品导购:51,奶茶店员:70,医药连锁:27,夜班8小时店员:38,店员:97,促销......
  • Leetcode3234. 统计 1 显著的字符串的数量
    EverydayaLeetcode题目来源:3234.统计1显著的字符串的数量解法1:枚举左端点注意到,如果子串中的0非常多,多到0的个数的平方比1的个数都要大,那么这样的子串必然不是1显著子串。设cnt0为子串中的0的个数,cnt1为子串中的1的个数,那么必须满足:cnt0*cnt0<=......
  • Java:有效括号字符串验证器
    Java实现的有效括号字符串验证器引言在编程中,经常需要验证一组字符串中的括号是否正确配对。例如,检查一段代码或表达式中的圆括号、方括号和花括号是否成对出现。这类问题不仅在编程语言解析器中非常重要,也是许多软件开发场景中的基础需求。本文将介绍一种基于Java语言实......
  • 【3.10】贪心算法-找出对应 LCP 矩阵的字符串
    一、题目对任一由n个小写英文字母组成的字符串word,我们可以定义一个nxn的矩阵,并满足:lcp[i][j]等于子字符串 word[i,...,n-1]和word[j,...,n-1]之间的最长公共前缀的长度。给你一个nxn的矩阵lcp。返回与lcp对应的、按字典序最小的字符串 word。如果......
  • 高级字符串算法
    目录最长公共子串/子序列最长公共子串算法步骤代码示例复杂度分析最长公共子序列算法步骤代码示例复杂度分析正则表达式匹配正则表达式语法代码示例NFA与DFA在正则表达式匹配中的应用NFA(非确定性有限自动机)DFA(确定性有限自动机)NFA与DFA的比较字符串编辑距离(Le......
  • MySQL中日期和时间戳的转换:字符到DATE和TIMESTAMP的相互转换
    在MySQL中,经常需要在DATE、TIMESTAMP和字符串之间进行相互转换。以下是一些常见的转换方法:1.字符串到日期/时间类型字符串转DATE:使用STR_TO_DATE()函数将字符串转换为DATE类型。你需要提供字符串的格式。SELECTSTR_TO_DATE('2024-08-24','%Y-%m-%d')ASmy_......