Problem of the Day -- Longest Palindrome

Longest Palindrome

A few days ago we looked at palindromic numbers. A palindrome is a string that reads the same forwards as it does backwards. Our goal today is to write a function that takes in a string and returns the longest palindrome in that string.

For example, the longest palindrome in "Max drives a racecar after work" is "a racecar a".

Fun fact: This can be solved in linear time o(n), though a naive, quadratic solution is perfectly fine

Permalink: http://problemotd.com/problem/longest-palindrome/

Comments:

Anonymous - 10 years, 9 months ago
My Solution in C++

include "afx.h"

int ReverseCompare(CString* String, int SLength);

void main(void) { printf("Please write your String and the program will search for the longest palindrome!\n"); CString String; scanf("%[^\t\n]", String); String.Format("%s", String); for(int i=String.GetLength();i>=1;i--) {
if(int found = ReverseCompare(&String,i)) { printf("The longest palindrome found in your String is \"%s\"!\n", String.Mid(found,i)); return; }
```
}
printf("Unfortunately there was no palindrome found in your String!");
```
}

int ReverseCompare(CString* String1, int SLength) { CString String1temp, String2temp; int StrLength = String1->GetLength(); int nOffset = StrLength - SLength; do { String2temp = String1temp = String1->Mid(nOffset,SLength); String2temp.MakeReverse(); if(!String1temp.CompareNoCase(String2temp)) return nOffset; else nOffset--;
```
}while(nOffset >= 0);

return 0;
```
}

reply permalink

Anonymous - 10 years, 9 months ago

#include "afx.h"

int ReverseCompare(CString* String, int SLength);

void main(void) {
    printf("Please write your String and the program will search for the longest palindrome!\n");
        CString String; scanf("%[^\t\n]", String);
    String.Format("%s", String);
    for(int i=String.GetLength();i>=1;i--) {
        if(int found = ReverseCompare(&String,i)) {
            printf("The longest palindrome found in your String is \"%s\"!\n", String.Mid(found,i));
            return;
        }

    }
    printf("Unfortunately there was no palindrome found in your String!");

}

int ReverseCompare(CString* String1, int SLength) {
    CString String1temp, String2temp; int StrLength = String1->GetLength();
    int nOffset = StrLength - SLength;
    do { String2temp = String1temp = String1->Mid(nOffset,SLength);
        String2temp.MakeReverse();
        if(!String1temp.CompareNoCase(String2temp))
            return nOffset;
        else
            nOffset--;

    } while(nOffset >= 0);

    return 0;

}

reply permalink

Pearce Keesling - 10 years, 9 months ago

I'm really curious to know what the proper way to do it is. I'm sure my way is extremely inefficient, but better than nothing ;).

#include <iostream>
#include <cstring>
#include <string>

using namespace std;

bool isPalindrome(string str)
{
    string::iterator fwd = str.begin();
    for(string::reverse_iterator bkwd = str.rbegin();bkwd < str.rend();bkwd++)
    {
        if(*fwd != *bkwd)return false;
        fwd ++;
    }
    return true;
}

int main(int argc, char* argv[])
{
    string max("");
    for(char* c = argv[1]; c < argv[1] + strlen(argv[1]);c++)
    {
        string buff("");
        for(char* d = c; d < argv[1] + strlen(argv[1]);d++)
        {
            buff += *d;
            if(isPalindrome(buff) && buff.size() > max.size()) max = buff;

        }
        buff.clear();
    }
    cout << max << endl;
    return 0;
}

C++ if you couldn't guess :)

reply permalink

Max Burstein - 10 years, 9 months ago

Thanks for posting! A really good write up on the problem can be found here http://www.akalin.cx/longest-palindrome-linear-time (python). The wikipedia page also has a pretty good explanation http://en.wikipedia.org/wiki/Longest_palindromic_substring (java).

reply permalink
Pearce Keesling - 10 years, 9 months ago
That was a great read, thanks :)

reply permalink

Asandwich - 10 years, 9 months ago

My solution in Java. I'm not to sure of runtime, I think it's the quadratic solution.

public class PalindromeFinder {
    public static void main(String[] args)
    {
        PalindromeFinder pf = new PalindromeFinder();
        System.out.println(pf.findPalindrome("Max drives a racacar after work."));
    }

    public String findPalindrome(String s)
    {
        String result = "";
        for(int i = 0; i < s.length()-1; i++)
        {
            int i0 = i;
            int i1 = i+1;
            char c0 = getChar(s, i0);
            char c1 = getChar(s, i1);
            String temp = "";

            if(c0 != c1) {
                temp = temp + c0;
                i0--;
                c0 = getChar(s,i0);
            }
            while(c0 != '\0' && c1 != '\0' && c0 == c1)
            {
                temp = c0 + temp + c1; 
                i0--;
                i1++;
                c0 = getChar(s,i0);
                c1 = getChar(s, i1);
            }
            if(temp.length() > result.length())
                result = temp;
        }
        return result;
    }

    private static char getChar(String s, int i) {
        if(i < 0 || i > s.length() -1)
            return '\0';
        return s.charAt(i);
    }
}

reply permalink

tehmagik - 10 years, 9 months ago

Here's a python version:

import math

#find longest palindrome in a string
def LongestPalindrome(word):
    longest = ""
    word = MakeOddLength(word)
    #you can skip the first 2 'letters'
    for index in range(2,len(word)-1):
        tmp = CheckPalindrome(word, index)
        if tmp:
            if len(tmp) > len(longest):
                longest = tmp
    return RemovePlaceholders(longest, "#")

def MakeOddLength(word):
    oddWord = ""
    for letter in word:
        oddWord += "#"+letter
    oddWord += "#"
    return oddWord

def RemovePlaceholders(word, placeholder):
    newWord = ""
    for letter in word:
        if letter != placeholder:
            newWord += letter
    return newWord

def CheckPalindrome(word, index):
    palindrome = ""
    for i in range(0, len(word)):
        if(index + i >= len(word) or index - i < 0):
            break
        if(word[index-i] != word[index+i]):
            return palindrome
        else:
            palindrome = word[(index-i):(index+i)]
    return palindrome


print(LongestPalindrome("Max drives a racecar afterwork"))

reply permalink

Anonymous - 10 years, 9 months ago

Short one in J.

longestpalindrome=: 3 : 0
  infixes=. ; <@(<\)\. (#~ ' '&~:) tolower y
  palindromes=. (; (-:|.)&.> infixes) # infixes
  palindromes {::~ (i. >./) #@> palindromes
)

longestpalindrome 'Max drives a racecar after work'  NB. => 'aracecara'

reply permalink

Anonymous - 10 years, 9 months ago

Seems like I had misunderstood the requirements. Here's a better one.

longestpalindrome=: monad define
  palindromes=. (#~ (-:|.)@>) ; <@(<\)\. y
  ((i. >./) #@> palindromes) {:: palindromes
)

longestpalindrome 'Max drives a racecar after work'  NB. => 'a racecar a'

reply permalink

John - 10 years, 9 months ago

I think I got a linear solution in javascript, but it could be a BAD linear solution, but it's one map and one reduce.

Usage: longestPalindromeIn("Max drives a racecar after work"); // "a racecar a"

function longestPalindromeIn(input) {
    var palArr = input.split('');
    return palArr.map(function(e,i){ return longestPalindromeAt(i);}).reduce(function(p,c){ return p.length>=c.length ? p: c;},'');

    function fromPalArr(index,length) {
       return palArr.slice(index-Math.floor(length/2),index+Math.ceil(length/2)).join('');
    }

    function palindromeAt(index, length){
       if (Math.min(index, palArr.length-index) - Math.floor(length/2) >= 0) {
          if (length %2 == 0) {
             for (var i = 1; i <= length/2; i++) {
                if (palArr[index-i] != palArr[index+i-1]){
                   return false;
                }
             }
             return true;
          }
          if (length %2 == 1) {
             for (var i = 1; i <= length/2; i++) {
                if (palArr[index-i] != palArr[index+i]){
                   return false;
                }
             }
             return true;
          }
       }
       return false;
    }

    function longestPalindromeAt(index) {
       var i = 1;
       if (palindromeAt(index, 2)) {
          i = 2;
       } else if (palindromeAt(index,3)) {
          i = 1;
       } else {
          return fromPalArr(index,1);
       }
       while(palindromeAt(index,i)) {
         i += 2;
       }
       return fromPalArr(index,i-2);
    }
}

PS, you can hit F12, and copy/paste mine to the console to test it right on the page.

reply permalink

Hueho - 10 years, 9 months ago

In Ruby

def palindrome(str)
  len = str.size / 2
  cut = len.even? ? len : len + 1
  str[0, len] == str[cut, len].reverse
end

def longest_palindrome(str)
  max = str.size - 1
  result = ""

  0.upto(max).each do |i|
    0.upto(max).each do |j|
      test = str[i..j]
      result = test if palindrome test and test.size > result.size
    end
  end

  result
end

puts longest_palindrome("Max drives a racecar after work")

reply permalink

gulliver - 10 years, 9 months ago

def palindrome(sentence):
    import numpy as np
    sentence = sentence.replace(' ','') # to remove white space
    sentence = sentence.upper()
    array_size = len(sentence) + 1 # add 1 for border that is zeroed out
    array = np.zeros((array_size,array_size))

    max_col = array_size-1
    max_score = 0
    for i in range(1,array_size):
        for j in range(array_size-2,-1,-1):
            if sentence[j] == sentence[i-1]:
                array[i][j] = array[i-1][j+1] + 1
                if array[i][j] > max_score:
                    max_score = array[i][j]
                    max_col = j
    print sentence[max_col:max_col+int(max_score)]

reply permalink

Content curated by @MaxBurstein

Problem of the Day A new programming or logic puzzle every Mon-Fri

Longest Palindrome

Comments:

include "afx.h"

Problem of the Day
A new programming or logic puzzle every Mon-Fri