首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

无重复字符的最长子串“Leetcode递归解决方案不起作用

无重复字符的最长子串是一个经典的算法问题,要求找出给定字符串中最长的不包含重复字符的子串的长度。

对于该问题,可以使用滑动窗口的思想进行解决。具体步骤如下:

  1. 定义两个指针,分别指向子串的起始位置和结束位置,初始时起始位置和结束位置都为字符串的第一个字符。
  2. 使用一个哈希集合来记录当前子串中出现过的字符。
  3. 当结束指针遍历到字符串的末尾时,算法结束。
  4. 如果当前子串中的字符在哈希集合中不存在,表示该字符是一个新字符,将该字符加入到哈希集合中,并更新最长子串的长度。
  5. 如果当前子串中的字符在哈希集合中存在,表示出现了重复字符,此时需要将起始指针向右移动,直到将重复字符从子串中移除。
  6. 重复步骤4和5,直到结束指针遍历完整个字符串,记录下最长子串的长度。

下面是一个可能的实现代码:

代码语言:txt
复制
def lengthOfLongestSubstring(s):
    start = 0
    end = 0
    max_length = 0
    char_set = set()

    while end < len(s):
        if s[end] not in char_set:
            char_set.add(s[end])
            end += 1
            max_length = max(max_length, end - start)
        else:
            char_set.remove(s[start])
            start += 1

    return max_length

该算法的时间复杂度为O(n),其中n为字符串的长度。

该算法的应用场景包括字符串处理、文本分析、数据挖掘等领域。在实际开发中,可以使用腾讯云的云服务器、容器服务、函数计算等产品来支持算法的部署和运行。

注意:本回答中并未提及具体的腾讯云产品和产品介绍链接地址,请根据具体需求选择适合的产品。

页面内容是否对你有帮助?
有帮助
没帮助

相关·内容

LeetCode无重复字符的最长子串

LeetCode第三天 好不甘心,夏天就这么过去了 ,但是LeetCode之旅才刚刚拉开序幕。 题目 今天带来的是第三题: ?...什么是子串 串中任意个连续的字符组成的子序列称为该串的子串 对于一个字符串变量,例如"adereegfbw",它的子串就是像"ader"这样可以从中找到的连续的字符串。...字符串"adereegfbw"本身也属于它本身最长的子串。...ab的子串:a、b、ab和一个空子串共4个即(2+1+1)个,abc的子串:a、 b、 c、 ab、 bc 、abc和一个空子串 共(3+2+1+1)个,所以若字符串的长度为n,则子串的个数就是[n*(...言归正传题目中还有两个关键字不含有重复字符和最长 这里采用数组的方法,定义一个空队列,判断是否存在字符,如果重复则截取数组,如果不存在往定义好的队列里添加。

65220
  • Leetcode 无重复字符的最长子串

    无重复字符的最长子串 给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。 我的思路 & 实现 使用两个指针,分别为头指针和尾指针。...头指针指向无重复字符子串头部,一个指向子串尾部,初始时,两个指针都指向字符串第一个元素。...维护一个哈希表(查找效率高),存放当前子串已有元素 尾指针检查当前所指元素是否在当前子串中出现过(查找哈希表中是否有当前元素),如果不存在,将当前元素存入哈希表,尾指针后移,并更新最大长度;如果存在,说明已经找到了一个无重复字符的子串...优化 优化了之前的代码,性能大大提高 之前的代码在找到一个无重复字符子串后,采用make重新创建一个map的方法来清空原map,这个操作是费时的 由于采用了创建新的map来清空map,导致尾指针在寻找下一个无重复字符子串时需要返回到与头指针一样的位置...,这样就多了不必要的遍历,以及往map中添加元素的操作,很费时 在已经找到一个无重复字符子串之后,在头指针右移的过程中,同时删除map中相关的元素 这样就不需要新创建一个新map,也大大减少空间复杂度,

    14930

    【LeetCode】无重复字符串最长子串

    题目描述 给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。 示例 1: 输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。...示例 2: 输入: "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。...示例 3: 输入: "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。...题目解析 这道题的目标是找出最长子串,并且该子串必须不包含重复字符,而且这个子串必须是原字符串中连续的一部分(见示例3中的解释说明)。...拿到题目时先不要心急想什么骚操作,我们先从最普通的操作开始把题目解出来,然后再来看如何优化。

    1.1K10

    LeetCode(一)——无重复字符的最长子串

    题目: 题目:https://leetcode.cn/problems/longest-substring-without-repeating-characters/ 题目大意: 在一个字符串重寻找没有重复字母的最长子串...思路: 采用滑动窗口的思想进行解题,滑动窗口的右边界不断的右移,只要没有重复的字符,就持续向右扩大窗口边界;一旦窗口内出现了重复字符,就需要缩小左边界,直到重复的字符移出了左边界,然后继续移动滑动窗口的右边界...注意点: 无论有无重复字符,右边界都会向右持续移动 重复字符出现在窗口内idx>=left,才需要进行滑动左边界,如果出现在窗口外,就不要滑动左边界。...make(map[byte]int) for right < len(s) { if idx, ok := indexes[s[right]]; ok { // 这里需要注意,只有重复字符在窗口内部才需要滑动左边界

    18530

    【leetcode算法-无重复字符的最长子串】

    给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。 示例 1: 输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。...示例 2: 输入: "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。...System.out.println(Demo2.LengthOfLongestSubstring("ababedf")); } } 2、大佬解法 滑动窗口,通过使用 HashSet 作为滑动窗口,我们可以用 O(1) 的时间来完成对字符是否在当前的子字符串中的检查...滑动窗口是数组/字符串问题中常用的 抽象概念。 窗口通常是在数组/字符串中由开始和结束索引定义的一系列元素的集合,即 [i, j)(左闭,右开)。而滑动窗口是可以将两个边界向某一方向“滑动”的窗口。...此时,我们找到的没有重复字符的最长子字符串将会以索引 i开头。如果我们对所有的 i 这样做,就可以得到答案。

    1.4K20

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

    求真正的长度时要 +1,用三目运算判断当前最长的子串与已记录的最长子串的比较且重新定义最长子串,可能还是原来的最长,也可能是当前子串最长 max = max > (i - start...max : (i - start + 1); } // 返回遍历后的最终最长子串 return max; } } 题解分析   这道题要明确的一点是求最长子串而不是最长子序列...先对传进来的字符串长度进行判断,若传进来的字符串长度小于等于 1,则直接返回其长度即可,定义开始指针的位置,以及初始化最长字串的记录值,并将字符串转换为字符数组。...每两次循环执行完后都要让当前字串长度与已记录的最长子串长度进行比较,由于 start 从 0 开始的,求真正的长度时要 +1,用三目运算判断当前最长的子串与已记录的最长子串的比较且重新定义最长子串,可能还是原来的最长...待遍历完成后记录的最长字串即为所求,返回即可。 leetcode原题:3. 无重复字符的最长子串

    19640

    LeetCode-3 无重复字符的最长子串

    无重复字符的最长子串 > 难度:中等 > 分类:字符串 > 解决方案:双指针、滑动窗口 LeetCode前几道题都是经典题,今天我们学习第3题无重复字符的最长子串,这道题在秋招面试中遇见过,再次相遇...示例1: 输入: "abcabcbb"输出: 3 解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。...示例2: 输入: "bbbbb"输出: 1解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。...Github地址 LeetCode-3 无重复字符的最长子串:https://github.com/JacobLei/leetcode/blob/master/src/main/java/A3_LongestSubstringWithoutRepeatingCharacters.java...参考链接 无重复字符的最长子串:https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution

    42930
    领券