My O(N) algorithm in Java7 (280ms)


  • 0
    W
    public class Solution {
        public int lengthOfLongestSubstring(String s) {
        	int length = s.length();
        	Map<Character, Integer> map = new HashMap<>();
        	int lenLS = 0;
        	int j = -1;
            for (int i = 0; i < length; i++){
            	Integer pos = map.get(s.charAt(i));
            	if (pos != null && pos >= j){
            		lenLS = lenLS >= i - 1 - j ? lenLS : i - 1 - j;
            		j = pos;
    			}
            	map.put(s.charAt(i), i);
            }
            return lenLS < length - 1 - j ? length - 1 - j : lenLS;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.