Leetcode 3 Longest Substring Without Repeat... 最长无

RyanHoo 发布于2019-08-14 17:01 / 1944人阅读

摘要：难度题意是求最长无重复子串给出一个字符串从所有子串中找出最长且没有重复字母的子串的长度我的解法是以为例使用一个记录当前子串遇到的所有字符用一个游标从头开始读取字符加入到中如果碰到了重复字符遇到了重复则从当前子串的头部的字符开始将该字符从中移

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 the length of 1.
Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

难度: Medium

题意是求最长无重复子串, 给出一个字符串, 从所有子串中, 找出最长, 且没有重复字母的子串的长度.

我的解法是: (以abcbcdabb为例)

使用一个set, 记录当前子串遇到的所有字符.

用一个游标, 从头开始读取字符, 加入到set中.(a, ab, abc)

如果碰到了重复字符(i=3, 遇到了b, 重复), 则从当前子串的头部的字符开始, 将该字符从set中移除, 直到移除了当前这个重复字符为止. (abc, bc, c, cb)

期间记录不重复的最大长度.

遍历完整个字符串后, 输出最大长度.

由于使用了HashSet, 每个元素访问不超过两次(添加与移除), 所以算法时间复杂度为O(n).

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        // a set to record chars for current substring
        Set cset = new HashSet();
        // length of longest non-repeat substring
        int lgst = 0;
        // length of current substring
        int curLen = 0;
        for (int i = 0; i < s.length(); i++) {
            Character c = s.charAt(i);
            curLen++;
            // if encounters a duplicate character
            if (cset.contains(c)) {
                // record non-repeat length
                lgst = (curLen - 1) > lgst ? (curLen - 1) : lgst;
                // reduce character from the head of current substring,
                // until current repeat letter is removed
                for (int j = i - cset.size(); j < i; j++) {
                    curLen--;
                    cset.remove(s.charAt(j));
                    if (s.charAt(j) == c) {
                        break;
                    }
                }
            }
            cset.add(c);
        }
        lgst = curLen > lgst ? curLen : lgst;
        return lgst;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.lengthOfLongestSubstring("bbbbbb"));
        System.out.println(s.lengthOfLongestSubstring("abcabcbb"));
        System.out.println(s.lengthOfLongestSubstring("abcbcdabb"));
        System.out.println(s.lengthOfLongestSubstring("aab"));
        System.out.println(s.lengthOfLongestSubstring("dvdf"));
        System.out.println(s.lengthOfLongestSubstring("advdf"));
    }
}

main方法执行的测试结果为:

1
3
4
2
3
3

服务器托管云服务器 Without Longest LeetCode Substring

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/66376.html

leetcode 3 Longest Substring Without Repeating Cha

摘要：题目详情题目要求输入一个字符串，我们要找出其中不含重复字符的最长子字符串，返回这个最长子字符串的长度。对于字符串中的每一个字符，先判断中是否已经存在这个字符，如果不存在，直接将添加到，如果已存在，则新的字符串就从不含前一个字符的地方开始。题目详情 Given a string, find the length of the longest substring without repe...

xcold 2019-08-15 14:21 评论0 收藏0
LeetCode——Longest Substring Without Repeating Char

摘要：原问题我的沙雕解法无重复字母存在重复字母挨打最暴力的无脑解法，耗时。。。原问题 Given a string, find the length of the longest substring without repeating characters. Example 1: Input: abcabcbb Output: 3 Explanation: The answer is a...

forsigner 2019-08-26 13:31 评论0 收藏0
[Leetcode] Longest Substring Without Repeating Cha

摘要：哈希表是最自然的想法。在遍历字符串时，我们先根据哈希表找出该字符上次出现的位置，如果大于等于子字符串首，便更新子字符串首。结束后，将该字符新的位置放入哈希表中。 Longest Substring Without Repeating Characters 最新更新解法：https://yanjia.me/zh/2018/12/... Given a string, find the ...

FleyX 2019-08-14 12:18 评论0 收藏0
[Leetcode] Longest Substring with At Most 2 Distin

摘要：最新思路解法哈希表法复杂度时间空间思路我们遍历字符串时用一个哈希表，但这个哈希表只记录两个东西，一个字母和它上次出现的时的下标，另一个字母和它上次出现时候的下标。这个通过用哈希表记录字母上次出现的下标，来维护一个窗口的方法也可以用于。 Longest Substring with At Most Two Distinct Characters 最新思路解法：https://yanjia...

imccl 2019-08-14 12:36 评论0 收藏0
[LeetCode] Longest Substring Without Repeating Cha

摘要：建立数组，存储个字符最近一次出现的位置。首次出现某字符时，其位置标记为，并用无重复字符计数器记录无重复字符的长度，再在更新其最大值。循环完整个字符串后，返回最大值。 Problem Given a string, find the length of the longest substring without repeating characters. Examples: Given ...

CoderStudy 2019-08-14 15:48 评论0 收藏0