`
bcyy
  • 浏览: 1809605 次
文章分类
社区版块
存档分类
最新评论

Longest Substring Without Repeating Characters -- LeetCode

 
阅读更多
原题链接:http://oj.leetcode.com/problems/longest-substring-without-repeating-characters/
这道题用的方法是在LeetCode中很常用的方法,对于字符串的题目非常有用。 首先brute force的时间复杂度是O(n^3), 对每个substring都看看是不是有重复的字符,找出其中最长的,复杂度非常高。优化一些的思路是稍微动态规划一下,每次定一个起点,然后从起点走到有重复字符位置,过程用一个HashSet维护当前字符集,认为是constant操作,这样算法要进行两层循环,复杂度是O(n^2)。

最后,我们介绍一种线性的算法,也是这类题目最常见的方法。基本思路是维护一个窗口,每次关注窗口中的字符串,在每次判断中,左窗口和右窗口选择其一向前移动。同样是维护一个HashSet, 正常情况下移动右窗口,如果没有出现重复则继续移动右窗口,如果发现重复字符,则说明当前窗口中的串已经不满足要求,继续移动有窗口不可能得到更好的结果,此时移动左窗口,直到不再有重复字符为止,中间跳过的这些串中不会有更好的结果,因为他们不是重复就是更短。因为左窗口和右窗口都只向前,所以两个窗口都对每个元素访问不超过一遍,因此时间复杂度为O(2*n)=O(n),是线性算法。空间复杂度为HashSet的size,也是O(n). 代码如下:

public int lengthOfLongestSubstring(String s) {
    if(s==null && s.length()==0)
        return 0;
    HashSet<Character> set = new HashSet<Character>();
    int max = 0;
    int walker = 0;
    int runner = 0;
    while(runner<s.length())
    {
        if(set.contains(s.charAt(runner)))
        {
            if(max<runner-walker)
            {
                max = runner-walker;
            }
            while(s.charAt(walker)!=s.charAt(runner))
            {
                set.remove(s.charAt(walker));
                walker++;
            }
            walker++;
        }
        else
        {
            set.add(s.charAt(runner));
        }
        runner++;
    }
    max = Math.max(max,runner-walker);
    return max;
}
这道题思想在字符串处理的题中还是比较重要的,实现上主要是HashSet和数组index的操作。扩展的题目有Substring with Concatenation of All WordsMinimum Window Substring,思路是非常接近的,只是操作上会更加繁琐一些。

分享到:
评论

相关推荐

    LeetCode3 Longest Substring Without Repeating Characters

    Given a string, find the length of the longest substring without repeating characters. Examples: Given "abcabcbb", the answer is "abc", which the length is 3. Given "bbbbb", the answer is "b", with...

    leetcode题库-leetcode-web:以Web形式展示LeetCode题解,基于PythonFlask

    leetcode题库 LeetCode-Web 初始化 前端库依赖 下载,并将jquery-3.x.x.min.js移动到static目录下。 下载,并将semantic.min.js、semantic.min.css、components和themes...longest-substring-without-repeating-charac

    leetcode跳跃-leetcode:leetcode一天一次

    leetcode 跳跃 leetcode 动态规划,背包问题 01背包问题:416. Partition Equal Subset Sum 最长回文:5. Longest Palindromic Substring - 字数组余数:523. Continuous Subarray Sum - 无重复字符的最长子串:3. ...

    leetcode分类-leetcode:leetcode问题的代码

    leetcode 分类leetcode 问题分类 leetcode代码仓库,我的解题思路写在我的博客里: leetcode 代码库,我博客上的解题思路: mkdir 列表: 大批 #1:Two Sum #4:Median of Two Sorted Arrays 地图 #1:Two Sum #3:...

    leetcode答案-LeetCode-Longest_Substring_Without_Repeating_Characters:Leet

    答案LeetCode-Longest_Substring_Without_Repeating_Characters 这是LeetCode上“最长子串无重复字符”问题的解决方案。 问题描述:给定一个字符串,求没有重复字符的最长子串的长度。 示例 1:输入:“abcabcbb” ...

    LeetCode去除数组重复元素-Arithmetic-Swift:一些算法的swift实现

    LeetCode去除数组重复元素 Arithmetic-Swift 一些算法的swift实现 桶排序 冒泡排序 快速排序 ##正好看见LeetCode可以刷Swift的题目 开始慢慢刷 swift有playground 做起来还是相当方便的 已完成题目 ----2016.9.30 两...

    leetcode题库-LeetCode-Go:用GO回答LeetCode

    LeetCode-Go 理论基础 见Note 脑图 TODO 待填充 算法题 面试高频出现,以及一些非常经典重要的算法题优先 题目列表 No Title Link Solution Acceptance Difficulty Topics Solution 0001 Two Sum 46.1% Easy 0002 ...

    LeetCodeTrain:这是来自LeetCode的已解决任务的存储库

    //leetcode.com/problems/coin-change/ ProductOfArrayExceptSelf.java - //leetcode.com/problems/product-of-array-except-self/ LongestRepeatingCharacterReplacement.java - //leetcode.com/problems/longest-...

    javalruleetcode-LeetCode:LeetCode算法问题

    java lru leetcode Fighting for a job! 记录找工作期间搬运的题,全部使用Java实现,本人C++鶸 1 ...LeetCode ...LeetCode ...LeetCode ...LeetCode ...Characters LeetCode 13 Roman to Integer LeetCode 6 Zi

    leetcode2sumc-LeetCode-3.Longest_Substring_Without_Repeating_Characters

    LeetCode-3.Longest_Substring_Without_Repeating_Characters 给定一个字符串,找出没有重复字符的最长子字符串的长度。 示例 1: 输入:“abcabcbb” 输出:3 解释:答案是“abc”,长度为 3。 解决方案 Python3:...

    分割数组求最大差值leetcode-Leetcode-Road:LeetCode刷题记录

    分割数组求最大差值leetcode LeetCode 学习之路 记录自己完成LeetCode的代码和结果。 序号 中文名称 英文名称 通过率 难度 1 Two Sum 47.0% 简单 2 Add Two Numbers 36.0% 中等 3 Longest Substring Without ...

    javalruleetcode-leetcode-java:力码笔记

    leetcode-java leetcode刷题笔记 已做题目列表 1.Two Sum 3.Longest Substring Without Repeating Characters 5.Longest Palindromic Substring 20.Valid Parentheses 26.Remove Duplicates from Sorted Array 53....

    dna匹配leetcode-leetcode:leetcode刷题

    Longest Substring Without Repeating Characters 哈希表 双指针 滑动窗口 Substring with Concatenation of All Words 哈希表 注意匹配方向 Valid Sudoku 数组 遍历 Sudoku Solver 深度优先遍历 回溯 先检查后修改 ...

    程序员面试宝典LeetCode刷题手册

    3. Longest Substring Without Repeating Characters 4. Median of Two Sorted Arrays 7. Reverse Integer 9. Palindrome Number 11. Container With Most Water 13. Roman to Integer 15. 3Sum 16. 3Sum Closest 17...

    leetcodepython001-leetcode:https://leetcode.com/的解决方案

    leetcode Python 001 力码 ├── Algorithms │  ├── cpp │  │  ├── 001 - Two Sum.cpp │  │  ├── 002 - Add Two Numbers.cpp │  │  ├── 003 - Longest Substring Without Repeating ...

    lrucacheleetcode-leetcode-1:leetcode-1

    Without Repeating Characters 最长没有重复字符的子序列 记录各字符最近一次出现的位置 4. Median of Two Sorted Arrays 求两有序数列的中位数,可泛化为求两有序数列的第k位数,二分法 5. Longest Palindromic ...

    leetcode实现strstr-leetcode-js:js刷leetcode

    leetcode-js 记录刷leetcode分析过程,希望一点点进步! leetcode地址 刷题顺序 按照顺序刷第一遍,记录实现思路,自己的优化方案,并研究高票大佬的思路。 已完成题目归档 序号 题目 题解 实现(初步思路/优化思路/...

    gasstationleetcode-leetcode-rust:莱特代码休息

    3-longest-substring-without-repeating-characters 7 cargo run --bin 7-reverse-integer 9 cargo run --bin 9-palindrome-number 13 cargo run --bin 13-roman-to-integer 14 cargo run --bin 14-longest-common-...

    华为leetcode-ProgrammingExercises:Leetcode和NewCoder练习

    华为 leetcode mistake-collection This is mistake collection for exercise publoms ...Source2:LeetCode ...Substring Without Repeating Characters code_6.org 二进制链表转整数 code_7.org 最小高度树

    leetcode中国-LeetCode-Swift:LeetCode算法题Swift实现

    LeetCode-Swift LeetCode算法题Swift实现 从2020年6月10日开始挑战每日刷算法,至少完成一道,让我们拭目以待! No. Title Chinese Difficulty Router 0001 Two Sum Easy 0002 Add Two Numbers Medium 0003 Longest ...

Global site tag (gtag.js) - Google Analytics