LeetCode3. 无重复字符的最长子串

题目链接：LeetCode3

题解

首先定义一个Map<Character,Integer>用来保存当前字符最后一次出现的下标位置。再定义一个pre数组，用来保存以每一个字符为结尾的最长无重复字符的子串。

接下来可以这么想，假设遍历到了下标i，i位置对应的字符为c，第一种情况，如果c从来没有在Map中出现过，并且i不为0(也就是说c不为首字符)，那么per[i] = pre[i - 1] + 1，并且把<c,i>放入Map中。

第二种情况，c出现在Map中，并且通过Map.get(c)得到c最后一次出现的位置记为lastPos，记aPos = lastPos + 1，unRepeatLen = per[i - 1]，bPos = i - unRepeatLen，如果aPos >= bPos，则pre[i] = i - aPos + 1，否则pre[i] = i - bPos + 1，并且无论何种情况都要记得更新字符最后一次出现的位置

代码

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s.length() == 0)
            return 0;
        Map<Character,Integer> pos = new HashMap<Character,Integer>();
        int[] pre = new int[s.length()];
        char[] str = s.toCharArray();
        for(int i = 0;i < s.length();i++) {
            Integer lastPos = pos.get(str[i]);
            if(lastPos == null) {
                pre[i] = i == 0 ? 1 : pre[i - 1] + 1;
                pos.put(str[i],i);
            } else {
                int aPos = lastPos + 1;
                int repeatLen = pre[i - 1];
                int bPos = i - repeatLen;
                if(aPos >= bPos)
                    pre[i] = i - aPos + 1;
                else
                    pre[i] = i - bPos + 1;
                pos.put(str[i],i);
            }
        }
        int max = pre[0];
        for(int i : pre)
            max = Math.max(max,i);
        return max;
    }
}