Longest Substring Without Repeat

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.

大意就是找出字符串中最长的且连续不重复的部分的长度

首先给出我自己的算法，先找出不重复字符的个数，假设个数就是结果，然后根据该个数循环截取输入字符串并判断截取后的字符串是不是符合要求，如果符合，返回长度，如果不符合将个数-1再次循环截取直到个数为0退出。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s == null || s.length() == 0){
            return 0;
        }
        char[] charArray = s.toCharArray();
        int maybeMaxLength = getMaybeMaxLength(charArray);
        if(maybeMaxLength > 1){
            int maxLength = 0 ;
            while(maybeMaxLength > 0){
                maxLength = findMaxLength(maybeMaxLength, charArray, s);
                if(maxLength == 0){
                    maybeMaxLength -- ;
                }else{
                    break;
                }
            }
            return maxLength;
        }else{
            return maybeMaxLength;
        }
    }

    private int findMaxLength(int maybeMaxLength, char[] charArray, String s){
        int maxLength = 0 ;
        for(int i = 0 ; i + maybeMaxLength <= charArray.length; i++){
            String substr = s.substring(i, i + maybeMaxLength);
            if(allUnique(substr)){
                maxLength = substr.length();
                break;
            }
        }
        return maxLength;
    }

    private boolean allUnique(String str){
        char[] charArray = str.toCharArray();
        return charArray.length == getMaybeMaxLength(str.toCharArray());
    }

    private int getMaybeMaxLength(char[] charArray){
        Set<Character> set = new HashSet<Character>();
        for(int i = 0; i< charArray.length; i++){
            set.add(charArray[i]);
        }
        return set.size();
    }
}

双重for循环时间复杂度为O(n2)

接下来给出leetcode推荐算法

/**
     * 1.基于这样一个事实：如果一个字符串中没有重复的字符，那么只需要判断新加入的字符不与字符串中任意一个字符不重复即可
     * 2.可以使用Map的containsKey方法(O(1))来判断重复字符
     * 3.对于S[j]元素在S[i,j)中发现重复的字符(假设该字符的索引位置是j')，那么我们可以忽略[i,j']间的所有元素
     * 直接将i设置为j'+1并继续循环
     * @param s
     * @return
     */
/**
         * i记录的是终止位置
         * j记录的是起始位置
         * 当发现重复的字符时，我们调整起始位置j=Math.max(j, map.get(s.charAt(i)))
         * 为什么是j和map.get(s.charAt(i))中的最大值而不是map.get(s.charAt(i))？
         * 考虑这种情况"abba",当i=2时我们找到了重复的字符b，那么我们设置j=1,当i=3时我们又找到了重复字符a，但是对于当前起始位置为1来说
         * map中的重复字符在1之前，所以并不能算是重复，所以不需要重置起始位置
         * 每次循环都要更新结果 = Math.max(i - j + 1(当前长度) , result)
         * 其实就是一次循环设置两个指针，i指针自增，j指针当发现重复字符时重新设置新位置，新位置通过Map来记录
         */
    public int lengthOfLongestSubstring(String s) {
        int ans = 0;
        Map<Character, Integer> map = new HashMap<>();
        for(int i = 0, j = 0; j < s.length(); j++){
            if(map.containsKey(s.charAt(j))){
                i = Math.max(i, map.get(s.charAt(j)));
            }
            ans = Math.max(j - i + 1, ans);
            map.put(s.charAt(j), j + 1);
        }
        return ans;
    }

只循环一次，时间复杂度O(n)