3. Longest Substring Without Repeating Characters

2019-09-16

3. Longest Substring Without Repeating Characters

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

Example 1:

1
2
3
Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:

1
2
3
Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

1
2
3
4
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
19
class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s == null || s.length() < 1) return 0; // Base case
        Map<Character, Integer> uniqueChars = new HashMap(); // Unique characters DS
        int maxLen = 0; // Final result
        int start = 0 ; // Start of the count of length of substring
        for(int i = 0 ; i < s.length() ;i++){
            if(uniqueChars.containsKey(s.charAt(i))){   // If character already encountered, find the new start position of substring
                int index = uniqueChars.get(s.charAt(i));
                start = Math.max(index, start);
            }
                uniqueChars.put(s.charAt(i), i + 1); // New character store in DS
                if(i - start+1 > maxLen){  // Check if we have a new longest substring
                    maxLen = i - start + 1;
                }
            }
        return maxLen;
    }
}
-->