leetcode-3.无重复字符的最长子串

题目链接

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

代码

class Solution {
    public int lengthOfLongestSubstring(String s) {

        int n = s.length();

        // 字母上次出现的下标
        int[] charLastOccIndex = new int[128];
        Arrays.fill(charLastOccIndex, -1);

        int left = -1;
        int max = 0;

        for (int i = 0; i < n; i++) {

            char c = s.charAt(i);
            
            left = Math.max(left, charLastOccIndex[c] + 1);
            max = Math.max(max, i - left + 1);

            charLastOccIndex[c] = i;
        }

        return max;
    }
}

复杂度分析

• 时间复杂度: O(N)
• 空间复杂度: O(count) count 为字符集数量