剑指Offer Java版 面试题48：最长不含重复字符的子字符

题目：请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。假设字符串中只包含'a'~'z'的字符。例如，在字符串"arabcacfr"中，最长的不含重复字符的子字符串是"acfr"，长度为4。

参考答案

public int longestSubstringWithoutDuplication(String str) {
    if (str == null || str.length() == 0) {
        return 0;
    }
    int curLength = 0, maxLength = 0;
    int[] position = new int[26];
    for (int i = 0; i < position.length; i++) {
        position[i] = -1;
    }
    for (int i = 0; i < str.length(); i++) {
        int prevIndex = position[str.charAt(i) - 'a'];
        if (prevIndex < 0 || i - prevIndex > curLength) {
            curLength++;
        } else {
            if (curLength > maxLength) {
                maxLength = curLength;
            }
            curLength = i - prevIndex;
        }
        position[str.charAt(i) - 'a'] = i;
    }
    if (curLength > maxLength) {
        maxLength = curLength;
    }
    return maxLength;
}

复杂度分析

• 时间复杂度：O(n)。
• 空间复杂度：O(1)。

👉剑指Offer Java版目录
👉剑指Offer Java版专题