Description

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

Example 1:

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

Example 2:

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

Example 3:

1Input: s = "pwwkew"
2Output: 3
3Explanation: The answer is "wke", with the length of 3.
4Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Constraints:

  • 0 <= s.length <= 5 * 10^4
  • s consists of English letters, digits, symbols and spaces.

Solution

In this case, we can create a sliding window until we have found repeating character. The problem asks to make sure that we do not repeat the same character. To make sure we don’t do that, we have to save those somewhere like HashMap or HashSet so that lookup is quick. When we come across a character which is repeating, our window becomes invalid.

 1class Solution {
 2    public int lengthOfLongestSubstring(String s) {
 3        if (s == null || s.length() == 0) return 0;
 4        int maxLength = 0;
 5        int start = 0, end = 0;
 6        Set<Character> set = new HashSet<>();
 7        while (end < s.length()) {
 8            if (!set.contains(s.charAt(end))) {
 9                set.add(s.charAt(end));
10                end++;
11                maxLength = Math.max(maxLength, set.size());
12            } else {
13                set.remove(s.charAt(start));
14                start++;
15            }
16        }
17        return maxLength;
18    }
19}