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

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

• 假设字符串中只包含'a'~'z'之间的字符，例如在字符串"arabcacfr"中，最长的不含重复字符的子字符串是"acfr"，长度为4

思路一：
运用动态规划的思想去求最大的子字符串的长度，使用一个长度为26的数组，记录每个字符-a以后对应的Ascll值上一次出现的位置，即索引为字符-a以后的Ascll值，数值为上一次出现的位置，默认为-1，如果当前位置的字符没有在前面出现过，或者与上次出现索引的距离差大于当前的长度，即上次出现的不在当前字符里，则长度增1，否则长度为距离，每次记录下最长的长度。
代码如下：

public int findLongestSubstring(String str) {
        int curlen = 0;
        int maxlen = 0;
        int[] position = new int[26];
        for (int i=0;i<26;i++){
            position[i] = -1;
        }
        for (int j=0;j<str.length();j++){
            int preIndex = position[str.charAt(j)-'a'];
            int distance = j - preIndex;
            if (preIndex == -1 || distance > curlen) curlen++;
            else curlen = distance;
            //记录当前字符出现的位置
            position[str.charAt(j)-'a'] = j;
            if (maxlen < curlen) maxlen = curlen;

        }
        return maxlen;
    }

 /**
     * 优化
     * @param str
     * @return
     */
    public int findLongestSubstring1(String str) {
        int curlen = 0;
        int maxlen = 0;
        int preIndex = -1;
        int[] position = new int[26];
        for (int i=0;i<26;i++){
            position[i] = -1;
        }
        for (int j=0;j<str.length();j++){
            preIndex = Math.max(preIndex,position[str.charAt(j) - 'a']);
            //统一两种情况，第一次出现为加1，其他情况去距离更大的
            curlen = j - preIndex;
            //记录上次出现的位置
            position[str.charAt(j) - 'a'] = j;
            maxlen = Math.max(curlen,maxlen);
        }
        return maxlen;
    }