Solution 1: Time limit exceeded
Time: O(n^2), Space: O(n)
The look-backs lead to maximum O(n^2) time complexity.123456789101112131415161718192021222324252627282930public static int lengthOfLongestSubstring(String s) { if (s == null) return 0; int len = s.length(); if (len < 2) return len; HashMap<Character, Integer> map = new HashMap<>(); int left = 0; int right = 0; int max = 0; for (int i = 0; i < len; i++) { char current = s.charAt(i); if (map.containsKey(current)) { i = map.get(current); // ISSUE: look back left = i; right = i; map.clear(); max = max > right - left? max : right - left; } else { map.put(current, i); right++; }}max = max > right - left? max : right - left;return max;}
Solution 2: Accepted
Time: O(n), Space: O(n)
Store the previous result rather than looking back.
Interesting: change from String to StringBuilder does not bring any performance boost.
Using String1234567891011121314151617181920212223public class Solution { public int lengthOfLongestSubstring(String s) { int max = 0; String temp = ""; if (s.equals("") || s == null) return 0; for (int i = 0; i < s.length(); i++) { String current = s.charAt(i) + ""; if (temp.length() == 0 || temp.indexOf(current) == -1) { temp = temp + current; } else { max = max > temp.length()? max : temp.length(); temp = temp.substring(temp.indexOf(current) + 1, temp.length()) + current; // store previous result } } max = max > temp.length()? max : temp.length(); return max; }}
Using StringBuilder1234567891011121314151617181920212223public int lengthOfLongestSubstring(String s) { int max = 0; StringBuilder temp = new StringBuilder(); if (s.equals("") || s == null) return 0; for (int i = 0; i < s.length(); i++) { String current = Character.toString(s.charAt(i)); if (temp.length() == 0 || temp.indexOf(current) == -1) { temp.append(current); } else { max = max > temp.length()? max : temp.length(); String head = temp.substring(temp.indexOf(current) + 1, temp.length()) + current; temp.setLength(0); temp.append(head); } } max = max > temp.length()? max : temp.length(); return max;}
Solution 3: Accepted
Improved solution 1 without looking back.123456789101112131415161718public int lengthOfLongestSubstring(String s) { if (s == null) return 0; if (s.length() == 0) return 0; HashMap<Character, Integer> map = new HashMap<Character, Integer>(); int left = 0; int max = 0; for (int right = 0; right < s.length(); right++){ char current = s.charAt(right); if (map.containsKey(current)){ left = Math.max(left, map.get(current) + 1); // ignores the "current" char BEFORE the left pointer // left = map.get(current); // returns "7" in test case "adbccba" } map.put(current, right); max = Math.max(max, right - left + 1); } return max;}
Solution 4: Accepted
Improved solution 3, replacing hashmap with array. Even faster.1234567891011121314151617public static int lengthOfLongestSubstring2(String s) { if (s == null) return 0; if (s.length() == 0) return 0; int[] cache = new int[256]; // char int left = 0; int max = 0; for (int right = 0; right < s.length(); right++) { char current = s.charAt(right); if (cache[current] > 0) { left = Math.max(left, cache[current]); } cache[current] = right + 1; max = Math.max(max, right - left + 1); } return max;}
Test case 1
Solution 1: ~70ms
Solution 2: ~20ms
Solution 3: ~10ms
Solution 4: ~4ms
|
|