Write a function that returns the longest palindrome in a given string

Question

e.g "ccddcc" in the string "abaccddccefe"

I thought of a solution but it runs in O(n^2) time

Algo 1:

Steps: Its a brute force method

Have 2 for loops
for i = 1 to i less than array.length -1
for j=i+1 to j less than array.length
This way you can get substring of every possible combination from the array
Have a palindrome function which checks if a string is palindrome
so for every substring (i,j) call this function, if it is a palindrome store it in a string variable
If you find next palindrome substring and if it is greater than the current one, replace it with current one.
Finally your string variable will have the answer

Issues: 1. This algo runs in O(n^2) time.

Algo 2:

Reverse the string and store it in diferent array
Now find the largest matching substring between both the array
But this too runs in O(n^2) time

Can you guys think of an algo which runs in a better time. If possible O(n) time

user_626022 · Answer

Hi Here is my code to find the longest palindrome in the string. Kindly refer to the following link to understand the algorithm http://stevekrenzel.com/articles/longest-palnidrome

Test data used is HYTBCABADEFGHABCDEDCBAGHTFYW12345678987654321ZWETYGDE

 //Function GetPalindromeString

public static string GetPalindromeString(string theInputString)
 { 

        int j = 0;
        int k = 0;
        string aPalindrome = string.Empty;
        string aLongestPalindrome = string.Empty ;          
        for (int i = 1; i < theInputString.Length; i++)
        {
            k = i + 1;
            j = i - 1;
            while (j >= 0 && k < theInputString.Length)
            {
                if (theInputString[j] != theInputString[k])
                {
                    break;
                }
                else
                {
                    j--;
                    k++;
                }
                aPalindrome = theInputString.Substring(j + 1, k - j - 1);
                if (aPalindrome.Length > aLongestPalindrome.Length)
                {
                    aLongestPalindrome = aPalindrome;
                }
            }
        }
        return aLongestPalindrome;     
  }

user_9724432 · Answer

public static void main(String[] args) {
         System.out.println(longestPalindromeString("9912333321456")); 
}

    static public String intermediatePalindrome(String s, int left, int right) {
        if (left > right) return null;
        while (left >= 0 && right < s.length()
                && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return s.substring(left + 1, right);
    }


    public static String longestPalindromeString(String s) {
        if (s == null) return null;
        String longest = s.substring(0, 1);
        for (int i = 0; i < s.length() - 1; i++) {
            //odd cases like 121
            String palindrome = intermediatePalindrome(s, i, i);
            if (palindrome.length() > longest.length()) {
                longest = palindrome;
            }
            //even cases like 1221
            palindrome = intermediatePalindrome(s, i, i + 1);
            if (palindrome.length() > longest.length()) {
                longest = palindrome;
            }
        }
        return longest;
    }

user_6766084 · Answer

#longest palindrome
s='HYTBCABADEFGHABCDEDCBAGHTFYW123456789987654321ZWETYGDE'
out1=[]
def substring(x):
    for i in range(len(x)):
        a=x[i:]
        b=x[:-i]
        out1.append(a)
        out1.append(b)
        
    return out1

for i in range(len(s)):
    substring(s[i:])    
final=set([item for item in out1 if len(item)>2])
final
palind={item:len(item) for item in final if item==item[::-1]}
print(palind)
sorted(palind.items(),reverse=True, key=lambda x: x[1])[0]

{'DED': 3, '123456789987654321': 18, '67899876': 8, 'ABCDEDCBA': 9, '456789987654': 12, '34567899876543': 14, 'BCDEDCB': 7, 'ABA': 3, '5678998765': 10, '2345678998765432': 16, 'CDEDC': 5, '789987': 6, '8998': 4} ('123456789987654321', 18)

user_4295595 · Answer

Program to find the longest substring which is palindrome from a given string.

 package source;
    
    import java.util.ArrayList;
            
    public class LongestPalindrome 
    {
        //Check the given string is palindrome by 
        public static boolean isPalindrome (String s)
        {
            StringBuffer sb = new StringBuffer(s);
            if(s.equalsIgnoreCase(sb.reverse().toString()))
                return true;
            else
                return false;
        }
    
        public static void main(String[] args) 
        {
            //String / word without space
            String str = "MOMABCMOMOM"; // "mom" //abccbabcd
            
            if(str.length() > 2 )
            {
                StringBuffer sb = new StringBuffer();
                ArrayList allPalindromeList = new ArrayList<>();
                        
                for(int i=0; i 2)
                    System.out.println("Maximum Length Palindrome SubString is : "+allPalindromeList.get(indexMaxSubStr));
                else
                    System.out.println("Not able to find a Palindrome who is three character in length!!");
            
            }
        }
    
    }

Write a function that returns the longest palindrome in a given string

23 Answers