Recursion: Longest Palindrome Substring

Question

This is a very common problem in which we would have to find the longest substring which is also a palindrome substring for the given input string.

Now there are multiple possible approaches to this and I am aware about Dynamic programming solution, expand from middle etc. All these solutions should be used for any practical usecase.

I was experimenting with using recursion to solve this problem and trying to implement the simple idea.

Let us assume that s is the given input string and i and j represent any valid character indexes of input string. So if s[i] == s[j], my longest substring would be:

s.charAt(i) + longestSubstring(s, i + 1, j - 1) + s.charAt(j)

And if these two characters are not equal then:

max of longestSubstring(s, i + 1, j) or longestSubstring(s, i, j - 1)

I tried to implement this solution below:

// end is inclusive
private static String longestPalindromeHelper(String s, int start, int end) {
    if (start > end) {
        return "";
    } else if (start == end) {
        return s.substring(start, end + 1);
    }
    // if the character at start is equal to end
    if (s.charAt(start) == s.charAt(end)) {
        // I can concatenate the start and end characters to my result string
        // plus I can concatenate the longest palindrome in start + 1 to end - 1
        // now logically this makes sense to me, but this would fail in the case
        // for ex: a a c a b d k a c a a (space added for visualization)
        // when start = 3 (a character)
        // end = 7 (again end character)
        // it will go in recursion with start = 4 and end = 6 from now onwards
        // there is no palindrome substrings apart from the single character
        // substring (which are palindrome by itself) so recursion tree for
        // start = 3 and end = 7 would return any single character from b d k
        // let's say it returns b so result would be a a c a b a c a a
        // this would be correct answer for longest palindrome subsequence but
        // not substring because for sub strings I need to have consecutive
        // characters
        return s.charAt(start)
                + longestPalindromeHelper(s, start + 1, end - 1) + s.charAt(end);
    } else {
        // characters are not equal, increment start
        String s1 = longestPalindromeHelper(s, start + 1, end);
        String s2 = longestPalindromeHelper(s, start, end - 1);
        return s1.length() > s2.length() ? s1 : s2;
    }
}

public static String longestPalindrome(String s) {
    return longestPalindromeHelper(s, 0, s.length() - 1);
}

public static void main(String[] args) throws Exception {
    String ans = longestPalindrome("aacabdkacaa");
    System.out.println("Answer => " + ans);
}

For a moment let us forgot about time complexity or runtime. I am focused towards making it work for simple case above. As you can see in the comments I got the idea why this is failing but I tried hard to rectify the problem following the exactly same approach. I don't want to use loops here.

What could be the possible fix for this following same approach?

Note: I am interested in the actual string as answer and not the length. FYI I had a look at all the other questions and it seems no one is following this approach for correctness so I am trying.

Answer 1

Once you have a call wherein s[i] == s[j], you could flip a boolean flag or switch to a modified method that communicates to child calls that they can no longer use the "don't match, try i + 1 and j - 1" branch (else condition). This ensures you're looking at substrings, not subsequences, for the remainder of the recursion.

Secondly, for the substring variant, even if s[i] == s[j], you should also try i + 1 and j - 1 as if these characters didn't match, because one or both of these characters might not be part of the final best substring between i and j. In the subsequence version, there's never any reason not to add any matching characters to the current palindromic subsequence for the range i to j, but that's not always the case with substrings.

For example, given input "aabcbda" and we're at a call frame where i = 1 and j = length - 1, we need to maximize over three possibilities:

1. The best substring includes both 'a' characters. Call the subroutine with the flag that says we have to consume from both ends on down and can no longer try skipping characters.
2. The best substring might still include s[i] but not s[j], try j - 1.
3. The best substring might still include s[j] but not s[i], try i + 1.

Another observation: it might make more sense to pass best indices up the helper call chain, then grab the longest palindromic substring based on these indices at the very end in the wrapper function.

On a similar note, if you're struggling, you might simplify the problem and return the longest palindromic substring length using your recursive method, then switch to getting the actual substring itself. This makes it easier to focus on the subsequence logic without the return value complicating things as much.

Answer 2

It is much easier to use loops here, rather than recursion, something like this:

public static void main(String[] args) {
    System.out.println(longestPalindrome("abbqa")); // bb
    System.out.println(longestPalindrome("aacabdkacaa")); // aca
    System.out.println(longestPalindrome("aacabdkaccaa")); // acca
}

public static String longestPalindrome(String str) {
    String palindrome = "";
    for (int i = 0; i < str.length(); i++) {
        for (int j = i; j < str.length(); j++) {
            String substring = str.substring(i, j);
            if (isPalindrome(substring)
                    && substring.length() > palindrome.length()) {
                palindrome = substring;
            }
        }
    }
    return palindrome;
}

public static boolean isPalindrome(String str) {
    for (int i = 0; i < str.length() / 2; i++) {
        if (str.charAt(i) != str.charAt(str.length() - i - 1)) {
            return false;
        }
    }
    return true;
}