longest palindrom non-dp
import java.io.*;
import java.util.*;
class Solution {
public static void main(String[] args) {
Solution solution =new Solution();
String[] input = {
null,
"",
"CBAABCD",
"BAABCC",
"AC",
"A",
"AABADFBD"
};
for(int i=0;i< input.length;i++) {
System.out.println("Input: " + input[i] +
", Result: " + solution.longestPalidromeLength(input[i]));
}
}
public int longestPalidromeLength(String input){
if(input==null || input.length() < 1) return -1;
int maxSoFar = Integer.MIN_VALUE;
for(int i=0;i<input.length();i++){
String palindrome = expand(input,i,i);
maxSoFar = Integer.max(palindrome.length(), maxSoFar);
palindrome = expand(input,i,i+1);
maxSoFar = Integer.max(palindrome.length(), maxSoFar);
}
return maxSoFar;
}
public String expand(String input, int low, int high) {
while( low >=0 && high < input.length() &&
input.charAt(low) == input.charAt(high)) {
low--; high++;
}
return input.substring(low+1,high);
}
}