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.
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;
}
}
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;
}
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;
}
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.
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;}}
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.
