面试题48(剑指offer)--最长不含重复字符的子字符串

题目：请从字符串中找出一个最长的不包含重复字符的子字符串，计算该子字符串的长度。

思路：

动态规划：定义f(i)为以第i个字符结尾时不包含重复字符的子字符串的最长长度，只有一个字符时f(0)=1，有两个字符且不相等时f(1)=2,f(n)当第n个字符在前面未出现过则f(n)=f(n-1)+1,当第n个字符在前面出现过时，比较它和上一次出现的距离d与f(n-1)大小，如果d<=f(n-1)说明以前出现的字符在f(n-1)对应的最长子字符串里，则f(n)=d,否则仍然有f(n)=f(n-1)+1。

代码：

    private static int method(String str){
        if (str==null||str.equals("")){
            return 0;
        }
        char[] buf=str.toCharArray();
        int len=buf.length;
        int[] dp=new int[len];
        dp[0]=1;
        HashMap<Character,Integer> map=new HashMap<>();
        map.put(buf[0],0);
        int max=dp[0];
        for (int i = 1; i <len ; i++) {
            if (map.get(buf[i])==null){
                dp[i]=dp[i-1]+1;
                map.put(buf[i],i);
            }else if (i-map.get(buf[i])<=dp[i-1]){
                dp[i]=i-map.get(buf[i]);
                map.put(buf[i],i);
            }else {
                dp[i]=dp[i-1]+1;
                map.put(buf[i],i);
            }
            if (dp[i]>max){
                max=dp[i];
            }
        }
        return max;
    }