剑指offer第二版-48.最长不含重复字符的子字符串（动态规划

本系列导航：剑指offer（第二版）java实现导航帖

面试题48：最长不含重复字符的子字符串

题目要求：
输入一个字符串（只包含a~z的字符），求其最长不含重复字符的子字符串的长度。例如对于arabcacfr，最长不含重复字符的子字符串为acfr，长度为4。

解题思路：
动态规划。用dp[]记录状态，dp[i]表示以下标为i的字符结尾不包含重复字符的最长子字符串长度。初始化dp[0] = 1，求maxdp。每次可以根据dp的前一个状态推导出后一个状态，因此可以省略dp数组，使用一个变量记录dp值，使用maxdp记录最大的dp值。

package chapter5;

/**
 * Created with IntelliJ IDEA
 * Author: ryder
 * Date  : 2017/8/12
 * Time  : 19:37
 * Description:最长不含重复字符的子字符串
 **/
public class P236_LongestSubstringWithoutDup {
    //动态规划
    //dp[i]表示以下标为i的字符结尾不包含重复字符的最长子字符串长度
    public static int longestSubstringWithoutDup(String str){
        if(str==null || str.length()==0)
            return 0;
        //dp数组可以省略，因为只需记录前一位置的dp值即可
        int[] dp = new int[str.length()];
        dp[0] = 1;
        int maxdp = 1;
        for(int dpIndex = 1;dpIndex<dp.length;dpIndex++){
            //i最终会停在重复字符或者-1的位置,要注意i的结束条件
            int i = dpIndex-1;
            for(;i>=dpIndex-dp[dpIndex-1];i--){
                if(str.charAt(dpIndex)==str.charAt(i))
                    break;
            }
            dp[dpIndex] =  dpIndex - i;
            if(dp[dpIndex]>maxdp)
                maxdp = dp[dpIndex];
        }
        return maxdp;
    }
    public static void main(String[] args){
        System.out.println(longestSubstringWithoutDup("arabcacfr"));
        System.out.println(longestSubstringWithoutDup("abcdefaaa"));

    }
}

运行结果

4
6