A solution in JAVA with O(n^2)


  • 0
    N
    public class Solution {
        public String longestPalindrome(String s) {
            
    		if (s==null)
    			return null;
    		
    		if (s.length()<=2)
    			return s;
    		
    		int max1 = 0,max2 = 0;
    		int cur1 = -1,cur2 = -1;
    		
            for(int i=1;i<s.length()-1;i++){
            	int count = 0;
            	for(int j=1;j<Math.min(i+1, s.length()-i);j++){
            		if (s.charAt(i+j)==s.charAt(i-j)) {
    					count++;
    				}else {
    					break;
    				}
            	}
            	if (count > max1) {
    				max1 = count;
    				cur1 = i;
    			}
            }
            
            for(int i=0;i<s.length()-1;i++) {
            	if (s.charAt(i)==s.charAt(i+1)) {
            		int count = 0;
            		for (int j = 1; j < Math.min(i+1,s.length()-i-1); j++) {
            			if (s.charAt(i+j+1)==s.charAt(i-j)) {
        					count++;
        				}else {
        					break;
        				}
    				}
            		
            		if (cur2==-1) {
    					cur2 = i;
    				}
            		
            		if (count > max2) {
        				max2 = count;
        				cur2 = i;
        			}
    			}
            }
            
            return (max1*2+1)>=(max2*2+2)?s.substring(cur1-max1, cur1+max1+1):s.substring(cur2-max2, cur2+max2+2);
            
        }
    }

Log in to reply
 

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