I created a recursive solution to the issue but the biggest bug is that it doesn't recognize that a small palindrome sandwiched with other characters all in between two identical characters isn't necessarily a palindrome

  public static int palindrome(String str)
  {
    str = str.toLowerCase();
    if (str.length() == 0)
      return 0;
    if (str.length() == 1)
      return 1;

    if (str.charAt(0) == str.charAt(str.length() - 1))
    {
      int pal = palindrome(str.substring(1, str.length() - 1));

      if (pal != 1 || str.length() <= 3)
        return 2   pal;
    }
    return Math.max(palindrome(str.substring(0, str.length() - 1)), palindrome(str.substring(1)));
  }

CodePudding user response：

The function returns the maximal palindrome length of all substrings.

Hence the error is the last if condition:

if (pal == str.length() - 2)
    return str.length();

One has a large palindrome when between equal chars all is a palindrome too.

Note that for a length of 2 or 3 this works too. The error was considering pal 2 instead of str.length().

One can logically proof this version by pre- and post-conditions on every statement.

CodePudding user response：

I chose to use two methods, to determine whether or not a substring is a palindrome, and the other to get the longest palindromic substring, just because that was easier for me. You don't need separate methods to make this work, though.

Depending on what type of cases you might get, this may work:

public static int recursiveLength(String s) {
        if (isPalindrome(s)) {
            return(s.length());
        }
        int left = recursiveLength(s.substring(1)); // Cuts the substring from the left
        int right = recursiveLength(s.substring(0, s.length()-1)); // Cuts the substring from the right
        int max = Math.max(left, right); // Calculates which was the longest substring
        return(max);
}

I wouldn't test anything higher than a length of 25 characters, though, because it takes a lot of time.