[AMAZON]Longest palindrome substring

Given a string S, find the longest palindromic substring in S.

Comments

  1. We can expand the string around its palindromic centre.There are a total of 2*n-1 palindromic centres in the string.This way all odd and even length palindromes are handled. Time complexity-O(n^2). Space complexity- O(1)

    The best known algorithm is linear time Manacher's Algorithm.
    Linear time with O(n) space complexity.

    ReplyDelete
  2. static String longestPalindrome(String string){
    if(string == null) return string;
    if(string.length() == 1) return string;

    String str = "";
    for (int i = 0; i < string.length(); i++) {
    str += "#" + string.charAt(i);
    }
    str += "#";

    int[] p = new int[str.length()];

    int maxIndex = -1;
    int maxValue = -1;
    for (int i = 0; i < str.length(); i++) {
    if(i == 0) p[i] = 1;
    else if(maxIndex > -1 && p[maxIndex]/2 + i > str.length()) continue;
    else{
    int c = 1;
    for (int j = i-1, k = i+1; j >= 0 && k < str.length(); j--,k++) {
    if(str.charAt(j) == str.charAt(k))
    c += 2;
    }
    p[i] = c;
    if(maxValue < c){
    maxIndex = i;
    maxValue = p[i];
    }
    }
    }
    str = str.substring(maxIndex-maxValue/2, maxIndex+maxValue/2+1).replaceAll("\\#", "");
    return str;
    }

    ReplyDelete

Post a Comment

Popular posts from this blog