My java solution with DP


  • 0
    X

    int dp[]=new int[s.length()];
    int i;

    	for(i=0;i<s.length();i++){
    		dp[i]=0;
    	}
    	if(s.length()<=1){
    		return s.length();
    	}
    	dp[0]=1;
    	int ans=1;
    	for(i=1;i<s.length();i++){
    		String str=s.substring(i-dp[i-1],i);
    		if(!str.contains(s.substring(i,i+1))){
    			dp[i]=dp[i-1]+1;
    			ans=ans>dp[i]?ans:dp[i];		
    		}else if(str.contains(s.substring(i,i+1))){
    			int j;
    			for(j=i-dp[i-1];j<i;j++){
    				if(s.charAt(j)==s.charAt(i)){
    					dp[i]=i-j;
    				}
    			}
    		}
    	}
    
    	return ans;

Log in to reply
 

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