[LeetCode] Problem 3 - Longest Substring Without Repeating Characters

Posted on | In ,

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

Example

No.1

Input: “abcabcbb”

Output: 3

Explanation: The answer is “abc”, with the length of 3.

No.2

Input: “bbbbb”

Output: 1

Explanation: The answer is “b”, with the length of 1.

No.3

Input: “pwwkew”

Output: 3

Explanation: The answer is “wke”, with the length of 3. Note that the answer must be a substring, “pwke” is a subsequence and not a substring.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// O(n) runtime, O(1) space
public int lengthOfLongestSubstring(String s) {
    int[] ascii = new int[256];
    int max = 0;
    int idx = 0;

    Arrays.fill(ascii, -1);

    for (int i = 0; i < s.length(); i++) {
        if (ascii[s.charAt(i)] >= idx)
            idx = ascii[s.charAt(i)] + 1;

        ascii[s.charAt(i)] = i;
        max = Math.max(max, i - idx + 1);
    }

    return max;
}