Longest Substring Without Repeating Characters

Question

Given a string, find the length of the longest substring without repeating characters.

Example

For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3.

For "bbbbb" the longest substring is "b", with the length of 1.

Challenge

O(n) time

Tags

String Two Pointers Hash Table

Related Problems

Medium Longest Substring with At Most K Distinct Characters

Analysis

同样可以用窗口类型Two Pointers来解决，从两重for循环中优化算法，外层指针依次遍历，内层指针根据条件决定是否需要前进。

这样一类问题要熟练掌握思路：

for (i = 0; i < n; i++) {
    while (j < n) {
        if (满足条件)
            j++
            更行j状态
        else (不满足条件)
            break
    }
    更新i状态
}

Solution

public class Solution {
    /**
     * @param s: a string
     * @return: an integer
     */
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        HashSet<Character> hs = new HashSet<Character>();
        int ans = 0;

        int i = 0;
        int j = 0;
        for (i = 0; i < s.length(); i++) {
            while (j < s.length() && !hs.contains(s.charAt(j))) {
                hs.add(s.charAt(j));
                ans = Math.max(ans, j - i + 1);
                j++;
            }

            hs.remove(s.charAt(i));
        }
        return ans;
    }
}

LeetCode official: HashMap + Two Pointers

Instead of using a set to tell if a character exists or not, we could define a mapping of the characters to its index. Then we can skip the characters immediately when we found a repeated character.

Complexity Analysis

• Time complexity :O(n)O(n). Indexjjwill iteratenntimes.

• Space complexity (HashMap) :O(min(m,n))O(min(m,n)). Same as the previous approach.

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length(), ans = 0;
        Map<Character, Integer> map = new HashMap<>(); // current index of character
        // try to extend the range [i, j]
        for (int j = 0, i = 0; j < n; j++) {
            if (map.containsKey(s.charAt(j))) {
                i = Math.max(map.get(s.charAt(j)), i);
            }
            ans = Math.max(ans, j - i + 1);
            map.put(s.charAt(j), j + 1);
        }
        return ans;
    }
}

Reference

• Jiuzhang