# [Week Thirteen] Programming Contest - Longest Palindrome

Welcome back to the weekly programming contests! If you are new to the contest or need a refresher don’t forget to read up on the rules and information Posted Here

This week’s challenge is to write a method (you can call it anything you want) that takes in a String and returns the length of its longest substring that is a palindrome. Your method should also ignore all whitespace (u0020).

You can assume all letters are lowercase.

Examples:

longest(“howdy”) -> 1
longest(“good day”) -> 2
longest(“spongepowered”) -> 3
longest(“would you like a nut for a jar of tuna?”) -> 17
longest(“radar guns are cool”) -> 5
longest(“cart track”) -> 8
longest(“3.14159265358979323846264338327”) -> 5
longest(“7.07106781186547524400844362104”) -> 4

Also, if you like these weekly programming problems, please make some suggestions for the contest or specific challenges (in the main thread)! This takes time out of my Sunday and its not always fun! Using suggested challenges makes it a lot faster and easier for me.

Imports are allowed for this challenge!

Challenge Closes: Sunday 1/31/16

Good luck!

Test class:

``````public class Palindrome {
public static void main(String[] args) {
Map<String, Integer> tests = new HashMap<String, Integer>() {{
put("howdy", 1);
put("good day", 2);
put("spongepowered", 3);
put("would you like a nut for a jar of tuna?", 17);
put("radar guns are cool", 5);
put("cart track", 8);
put("3.14159265358979323846264338327", 5);
put("7.07106781186547524400844362104", 4);
}};

int passed = 0;
for (Map.Entry<String, Integer> entry : tests.entrySet()) {
String str = entry.getKey();
Integer expected = entry.getValue();
int actual = l(str);
System.out.printf("longest(\"%s\") -> %d", str, actual);
if (actual != expected) {
System.out.printf(", expected %d%n", expected);
} else {
System.out.println();
passed++;
}
}
System.out.printf("Passed %d out of %d tests%n", passed, tests.size());
}

// Replace this method with your own
public static int l(String s) {
return 0;
}
}
``````

The test condition for “Would you like a nut for a jar of tuna?” should be 17.

248 characters:

``````public static int p(String s){String t="";for(char c:s.toCharArray())if(c>32)t+=c;int o=0,l=t.length(),i,j,k;for(i=0;i<l;i++)l:for(j=i;j<=l;j++){s=t.substring(i,j);for(k=0;k<j-i;k++)if(s.charAt(k)!=s.charAt(j-i-k-1))continue l;o=k>o?k:o;}return o;}
``````

Readable version, with a few tweaks to make my intent clearer:

``````public static int palindrome(String in) {
String base = "";
// Strip whitespace.
for (char c : in.toCharArray()) {
if (!Character.isWhitespace(c)) {
base += c;
}
}

int out = 0;
for (int start = 0; start < base.length(); start++) {
loop: for (int end = start; end <= base.length(); end++) {
String substring = base.substring(start, end);
int index;
// Sadly, there's no reverse() method for String, so I'll need to inline it.
for (index = 0; index < substring.length(); index++) {
if (substring.charAt(index) != substring.charAt(substring.length() - index - 1)) {
// Not a palindrome
continue loop;
}
}
// It's a palindrome.
if (index > out) {
out = index;
}
}
}
return out;
}
``````

Think this one works.
Test: http://rextester.com/JENB19763

Minified (208 characters):
```Java`
public static int l(String s){char[]a=s.replace(" “,”").toCharArray();int r=0,i=0,l=a.length;for(;i<l;i++){int p=i,n=i,c=1;while(++n<l&&a[i]==a[n])c++;while(p>0&&n<l&&a[–p]==a[n++])c+=2;r=c>r?c:r;}return r;}

``````Readable:
```Java`
public static int longest(String input) {
char[] chars = input.replace(" ","").toCharArray();
int result = 0, pos = 0, length = chars.length;
/* Loop over each position in the array and compare chars either side of this position */
for (; pos < length; pos++) {
int previousPos = pos, nextPos = pos, count = 1;
/* The centre of this palindrome may be multiple characters wide, so increment
the starting position of 'nextPos' until a different character is found */
while(++nextPos < length && chars[pos] == chars[nextPos]) {
count++;
}
/* Compare characters at positions either side of the centre, increase count by two with
every match. Increment away from centre until positions do not hold matching characters */
while(previousPos > 0 && nextPos < length && chars[--previousPos] == chars[nextPos++]) {
count += 2;
}
/* Update result if count is bigger */
result = count > result ? count : result;
}
return result;
}
``````

Edited, thanks.

All whitespace (tabs, newlines, etc.) or just the space character (u0020)?

Just the space char, that’s why i put the code.

184 characters:

``````public static int l(String s){s=s.replace(" ","");int l=s.length(),m=l<1?0:1,i=0,j;for(;++i<l;)for(j=0;j<l-i;)if(s.charAt(j)==s.charAt(i+j++)&l(s.substring(j,i+j))>i-2)m=i+1;return m;}
``````

Readable:

``````public static int l(String s) {
s = s.replace(" ", "");
int l = s.length(), m = l < 1 ? 0 : 1, i = 0, j;
for (; ++i < l;)
for (j = 0; j < l - i;)
if (s.charAt(j) == s.charAt(i + j++) & l(s.substring(j, i + j)) > i - 2)
m = i + 1;
return m;
}
``````

It looks for matching characters in s which are the endpoints of a possible palindrome. To see whether the characters in between are a palindrome, it calls itself, passing in the substring between them. If the call returns the length of the string passed in, then it is a palindrome.

It recurses unconditionally for every pair of characters in s, so it does not complete the tests within a reasonable amount of time. However, it will complete the tests within a reasonable amount of time if a second ampersand is added after the first like so:

``````public static int l(String s) {
s = s.replace(" ", "");
int l = s.length(), m = l < 1 ? 0 : 1, i = 0, j;
for (; ++i < l;)
for (j = 0; j < l - i;)
if (s.charAt(j) == s.charAt(i + j++) && l(s.substring(j, i + j)) > i - 2)
m = i + 1;
return m;
}
``````

With a little thought, it should be clear that removing the second ampersand does not affect its correctness.

Meh, 225 characters

``````public static int l(String s){s=s.replace(" ","");for(int l=0,i=0,a=0,e=0;;i+=(a=i/2)+(e=a+i%2)>0?1:1){while(a>0&&e<s.length()&&s.charAt(a-1)==s.charAt(e)&&((a-=1)+(e+=1)>0||1>0));l=e-a>l?e-a:l;if(i+2>2*s.length())return l;}}
``````

Algorithm copied from Finding the Longest Palindromic Substring in Linear Time (`naiveLongestPalindromes`)

Congratulations to @eah for winning week thirteen and an honorable mention for @jus1in who came up with the shortest method but submitted late

The next challenge will be up shortly.

## 180 characters

Seems I was a bit too late posting this. Oh well.

``````public static int l(String s){s=s.replace(" ","");int m=s.length();return m<2||s.matches("(.).*\\1")&l(s.substring(1,m-1))>m-3?m:Math.max(l(s.substring(1)),l(s.substring(0,m-1)));}
``````

Unminified:

``````    public static int l(String s) {
s = s.replace(" ","");
int m = s.length();
return m < 2 ||
s.matches("(.).*\\1") & l(s.substring(1, m - 1)) > m - 3
? m
: Math.max(l(s.substring(1)), l(s.substring(0, m - 1)));
}
``````

It checks if length is less than two or the entire thing is a palindrome by checking that the first and last characters are the same and that calling itself on the substring without the first and last characters returns the length of the substring. If it is one of those things then it returns the length of the string. Otherwise it returns the maximum of calling itself on everything but the first character and everything but the last character. Its runtime is atrocious.

1 Like