public int lengthOfLongestSubstring(String s) {
    if (s == null || s.length() == 0) {
        return 0;
    }
    int len = s.length();
    int[] dp = new int[len]; // 以i结尾的最大子串的长度

    Map<Character, Integer> map = new HashMap<>();
    dp[0] = 1;//初始条件
    int res = dp[0]; //初始条件
    map.put(s.charAt(0), 0);//初始条件
    for (int i=1; i<len; i++) {

        if (map.containsKey(s.charAt(i))) {
            int d = i - map.get(s.charAt(i));
            if (d <= dp[i-1]) {
                dp[i] = d;
            } else {
                dp[i] = dp[i-1] + 1;
            }
            map.put(s.charAt(i), i); // 更新位置
        } else { // 没有包含
            map.put(s.charAt(i), i);
            dp[i] = dp[i-1]+1;
        }
        res = Math.max(res, dp[i]);
    }
    return res;
}

private int test(String s) {
    Map<Character, Integer> map = new HashMap<>(); // 存放字符对应位置
    int i=-1, res=0;
    for (int j=0; j<s.length(); j++) {
        if (map.containsKey(s.charAt(j))) {
            i = Math.max(i, map.get(s.charAt(j))); //更新位置
        }
        map.put(s.charAt(j), j); // 哈希表记录
        res = Math.max(res, j-i);// 更新结果
    }
    return res;
}

class Solution {
    public int lengthOfLongestSubstring(String s) {
        // 哈希集合，记录每个字符是否出现过
        Set<Character> occ = new HashSet<Character>();
        int n = s.length();
        // 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
        int rk = -1, ans = 0;
        for (int i = 0; i < n; ++i) {
            if (i != 0) {
                // 左指针向右移动一格，移除一个字符
                occ.remove(s.charAt(i - 1));
            }
            while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {
                // 不断地移动右指针
                occ.add(s.charAt(rk + 1));
                ++rk;
            }
            // 第 i 到 rk 个字符是一个极长的无重复字符子串
            ans = Math.max(ans, rk - i + 1);
        }
        return ans;
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/wu-zhong-fu-zi-fu-de-zui-chang-zi-chuan-by-leetc-2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。