Given a string, find the length of the longest substring without repeating characters.
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:
Time: O(n) Space: O(n)
public class Solution { public int lengthOfLongestSubstring(String A) { Set<Character> set = new HashSet<>(); int length = 0; for (int i = 0; i < A.length(); i ++) { char c = A.charAt(i); if (set.add(c)) { length = Math.max(length, set.size()); } else { int size = set.size(); for (int j = i - size; j < i; j ++) { char existing = A.charAt(j); if (existing == c) { break; } else { set.remove(existing); } } } } return length; } }
class Solution { public int lengthOfLongestSubstring(String s) { Map<Character, Integer> map = new HashMap<>(); int left = 0; int right = 0; int count = 0; while (right < s.length()) { char c = s.charAt(right); if (!map.containsKey(c)) { map.put(c, 1); count = Math.max(count, map.size()); } else { map.put(c, map.get(c) + 1); while (left < right) { char leftVal = s.charAt(left); map.put(leftVal, map.get(leftVal) - 1); if (map.get(leftVal) == 0) { map.remove(leftVal); } left ++; if (map.get(c) == 1) { break; } } } right ++; } return count; } }