Longest Substring Without Repeating Characters

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

Solution:

We use two pointers: left and right. Where left indicates the starting of the substring and right indicates the ending of the substring. If a character exists in map, we should increase the left pointer to remove the old one. The max length of the substring is max = Math.max(max, right - left + 1).

Code:

public class Solution {
    /**
     * @param s: a string
     * @return: an integer 
     */
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        boolean[] map = new boolean[256];
        int n = s.length();
        int j = 0;
        int res = 0;
        for (int i = 0; i < n; i++) {
            while (j < n && !map[s.charAt(j)]) {
                map[s.charAt(j)] = true;
                j++;
            }
            res = Math.max(res, j - i);
            map[s.charAt(i)] = false;
        }
        return res;
    }
}