[LeetCode] 3. Longest Substring without Repeating Characters

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

Examples:

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", 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.

Thought process:

Two pointers + sliding window:

• Pointer i points to the left end of current window.
• Pointer j points to the right end of current window.

Use a hash set to keep track of the characters in current window. Iterate through the string using j. If s[j] is a repeating character, increment i and remove s[i] from set until no repeating character is there.

Solution:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

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

Time complexity: O(n).