题目描述

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

假设字符串中只包含从 a 到 z 的字符。

样例

样例
输入："abcabc"

输出：3

算法1

(双指针) $O(n)$

从题目中可以看出是求最长子字符串的长度，因此第一个考虑是用动态规划来做，但是f(i)和f(i - 1)之间的关系不是很好对应，这题可以用双指针来做，因为这个情况下，两个指针都是单调递增的，因此用双指针的时间复杂度是 O(n),用hashmap来存储每个字母对应的次数，当一个字符加入之后，次数为两次，那么就是出现了重复，这个重复字符从指针i依次进行寻找，知道找到重读的字符，然后对应的hashmap中字母也要进行remove，然后计算 长度 k - i + 1；

Java 代码

class Solution {
    public int longestSubstringWithoutDuplication(String s) {
        int m = s.length();
        int i= 0;
        int res = 0;
        HashMap<Character,Integer> hash = new HashMap<Character,Integer>();
        for(int k = 0; k < m; k ++)
        {   
            char c = s.charAt(k);
            hash.put(c,hash.getOrDefault(c,0) + 1);
            if(hash.get(c) == 1) res = Math.max(res, k - i + 1);
            else {
                while(s.charAt(i) != c) 
                {
                    hash.remove(s.charAt(i));
                    i ++;
                }
                hash.remove(s.charAt(i));
                i ++;
                res = Math.max(res, k - i + 1);
                } 
        }
        return res;
    }

}