Longest Substring Without Repeating Characters-蒲公英云

Longest Substring Without Repeating Characters

冷不防 2022-06-08 08:13 214阅读 0赞

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.

思路：利用类似网络中的滑动窗口，

当新字符在窗口中没有出现时，将新字符加入窗口；

当新字符在窗口中出现过时，窗口的左边界移动到窗口中重复字符的右边。

public class Solution {
    public int lengthOfLongestSubstring(String s){
        if(s==null||s.length()==0){
            return 0;
        }
        if(s.length()==1){
            return 1;
        }
        char [] chars=s.toCharArray();
        int left=0,right=0;
        int max=1;
        while (right + 1 < chars.length) {
            int t = hasReapeat(chars, left, right, chars[right + 1]);
            if (t == -1) {
                ++right;
            } else {
                left = t;
            }
            if (right - left + 1 > max) {
                max = right - left + 1;
            }
        }
        return max;
    }
    public static int hasReapeat(char [] chars,int left,int right,char c){
        int ans=-1;
        for(int i=left;i<=right;++i){
            if(c==chars[i]){
                return i+1;
            }
        }
        return ans;
    }
}