[LeetCode] Longest Substring Without Repeating Characters

Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.
Solution 1: HashSet. This requires two iterations.
Sadly, Time Limit Exceeded.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

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

Solution 2: HashMap. Now this is only one iteration. 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

public class Solution { public int lengthOfLongestSubstring(String s) { if (s == null || s.length() == 0) { return 0; } HashMap<Character, Integer> map = new HashMap<>(); int i = 0; int j = 0; int maxLen = 0; while (j < s.length()) { if ( map.containsKey(s.charAt(j)) && map.get(s.charAt(j)) >= i ) { i = map.get(s.charAt(j)) + 1; } maxLen = Math.max(maxLen, j - i + 1); map.put(s.charAt(j), j); j++; } return maxLen; } }