2. Longest Substring Without Repeating Characters

Description

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

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

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

Example 3:
Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice 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.

Approach

• Time: O(n) Space: O(n)

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set<Character> data = new HashSet<>();
        int longest = 0;
        int start = 0;
 
        for (int end = 0; end < s.length(); end++) {
            while (data.contains(s.charAt(end))) {
                data.remove(s.charAt(start));
                start++;
            }
            data.add(s.charAt(end));
            longest = Math.max(longest, end - start + 1);
        }
 
        return longest;
    }
}