Longest Palindrome - O(n^2) time and O(1) extra space


public class LongestPalindrome {

    public static void main(String[] args) {
        lonPal("fasxabccba");
    }

    public static int lonPal(String s){
        int maxlen = 1;
       
        int start = 0;
        int len = s.length();
       
        int low, high;
       
        // for even length
        for(int i = 1; i <= len; i++){
            low = i;
            high = i + 1;
           
            while((low >= 0 && high < len) && (s.charAt(low) == s.charAt(high))){
                if(high - low + 1 > maxlen){
                    start = low;
                    maxlen = high - low + 1;
                }
                --low;
                ++high;
            }
        }
       
        // for odd length
        for(int i = 1; i <= len; i++){
            low = i - 1;
            high = i + 1;
           
            while((low >= 0 && high < len) && (s.charAt(low) == s.charAt(high))){
                if(high - low + 1 > maxlen){
                    start = low;
                    maxlen = high - low + 1;
                }
                --low;
                ++high;
            }
        }
        System.out.println(s.substring(start,start + maxlen));
        return maxlen;
    }
}

Comments

Popular posts from this blog

public vs protected vs default access modifiers - Java

Class, Reference and Object