题目描述

blablabla

样例

blablabla

算法1

$O(n)$

使用HashMap记录字符上次出现的位置，用pre记录最近重复字符出现的位置，则i(当前位置)-pre就是当前字符最长无重复字符的长度，取最大的就是字符串的最长无重复字符的长度

Java 代码

public int longestSubstringWithoutDuplication(String str) {
        if (str == null || str.length() < 1)
            return 0;

        // 记录字符上次出现的位置
        HashMap<Character, Integer> map = new HashMap<>();
        int max = 0;
        // 最近出现重复字符的位置
        int pre = -1;

        for (int i = 0, strLen = str.length(); i < strLen; i++) {
            Character ch = str.charAt(i);
            Integer index = map.get(ch);
            if (index != null)
                pre = Math.max(pre, index);
            max = Math.max(max, i - pre);
            map.put(ch, i);
        }

        return max;
    }