My java solution O(n) with hashtable


  • 2
    Y
    public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int maxlen=0;
    	 HashMap<String,Integer> map=new HashMap<String,Integer>();
    	 int curvaild=0,curlen=0;
    	 for(int i=0;i<s.length();i++){
    		 String ch=s.substring(i,i+1);
    		 if(map.containsKey(ch)&&map.get(ch)>=curvaild){
    			 curvaild=map.get(ch)+1;	//记录有效开始点,换新的位置,从重复点后一位开始
    			 if(curlen>maxlen) maxlen=curlen;	//更新最长距离
    			 curlen=i-map.get(ch);	//保存原始遗留的长度
    			 
    		 }else{
    			++curlen;				 
    		 }
    		 map.put(ch, i);
    	 }
    	  if(curlen>maxlen) maxlen=curlen;
    	 return maxlen;
    }
    

    }


Log in to reply
 

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