O(n^2) time complexity solution Not Accepted! ..kindly help


  • 0
    S
       public static String longestPalindrome(String inputStr)
    {
    	String longestPalindrome = "";
    	
    	int l = 0,r = 0; 
    	int len = inputStr.length();
    	//odd palindrome		
    	for(int i=0; i < len; i++)
    	{
    		l = i==0 ? 0 : i-1;
    		r = i== len-1 ? len-1 : i + 1;
    		
    		while(l >= 0 && r <= len - 1 && inputStr.charAt(l) == inputStr.charAt(r)){
    			if(r+1-l > longestPalindrome.length()){
    				longestPalindrome = inputStr.substring(l,r+1);				
    			}
    			
    			l--;
    			r++;
    		}
    		
    		if(i <= len - 2) 
    		if(inputStr.charAt(i) == inputStr.charAt(i+1)){	
    			 l = i==0 ? 0 : i -1;
    			 r = i == len - 1 ? len - 1 :  i + 2;
    			while(l >= 0 && r <= len-1 && inputStr.charAt(l) == inputStr.charAt(r)){
    				if(r-l+1 > longestPalindrome.length()){
    					longestPalindrome = inputStr.substring(l,r+1);
    				}
    				
    				l--;
    				r++;
    			}
    		}	
    		
    	}	
    	return longestPalindrome;
    }
    

    The above solution checks the odd and even palindromes !

    I solved it guys!...its TLE because there is a bettr way to do it-same approach but reducing constant time by checking if remaining characters in the for loop are smaller than the longest palindrome formed so far! If so stop looping :-) my friend gave this idea and it worked! havent added the single line above.i think u can figure it out :)


  • 0
    A

    well, same problem with you, I hope you have already solved it. If not, you can merge the two "while" in one, and it is ok.


  • 0
    S
    This post is deleted!

Log in to reply
 

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