题解 | #最长不含重复字符的子字符串#

import java.util.*;

/**
 * NC170 最长不含重复字符的子字符串
 * @author d3y1
 */
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @return int整型
     */
    public int lengthOfLongestSubstring (String s) {
        return solution1(s);
        // return solution2(s);
        // return solution3(s);
    }

    /**
     * 双指针
     * @param s
     * @return
     */
    private int solution1(String s){
        int len = s.length();
        if(len == 0){
            return 0;
        }

        int result = 0;
        HashSet<Character> set = new HashSet<>();
        char chL,chR;
        for(int i=0,j=0; i<=j&&j<len; j++){
            chR = s.charAt(j);
            if(!set.contains(chR)){
                result = Math.max(result, j-i+1);
            }else{
                while(set.contains(chR)){
                    chL = s.charAt(i++);
                    set.remove(chL);
                }
            }
            set.add(chR);
        }

        return result;
    }

    /**
     * HashMap
     * @param s
     * @return
     */
    private int solution2(String s){
        int left = -1, result = 0;
        HashMap<Character,Integer> map = new HashMap<>();

        for(int i = 0; i < s.length(); i++){
            if(map.containsKey(s.charAt(i))){
                left = Math.max(left, map.get(s.charAt(i)));
            }
            map.put(s.charAt(i),i);
            result = Math.max(result, i-left);
        }

        return result;
    }

    /**
     * 动态规划
     *
     * dp[i]表示以下标i结尾的最长不含重复子串的长度
     *
     * @param s
     * @return
     */
    private int solution3(String s){
        int len = s.length();
        if(len == 0){
            return 0;
        }

        int[] dp = new int[len];
        int result = 1;
        HashMap<Character, Integer> map = new HashMap<>();
        dp[0] = 1;
        map.put(s.charAt(0), 0);
        for(int i=1; i<len; i++){
            dp[i] = 1;
            if(!map.containsKey(s.charAt(i))){
                dp[i] = dp[i-1] + 1;
            }else{
                dp[i] = Math.min(dp[i-1]+1, i-map.get(s.charAt(i)));
            }
            map.put(s.charAt(i),i);

            result = Math.max(result, dp[i]);
        }

        return result;
    }
}