vamsu
8/4/2018 - 7:41 PM

Longest palindrome non-dp

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