Longest palindromic Substring length-CodePudding

Below code gives me longest palindromic subsequence length. How can I modify the code to get longest palindromic substring length?

public static int lp(String str, int i, int j, int ans) {    
    if (i == str.length() || j <= 0)
        return ans;

    if (i > j)
        return ans;

    if (i == j)
        return ans   1;

    if (str.charAt(i) == str.charAt(j)) {
        int a = lp(str, i   1, j, ans);
        int b = lp(str, i, j - 1, ans);
        int c = lp(str, i   1, j - 1, ans   2);
        ans = Math.max(Math.max(a, b), c);
        return ans;
    } else {
        int a = lp(str, i   1, j, ans);
        int b = lp(str, i, j - 1, ans);
        ans = Math.max(a, b);
        return ans;
    }
}

Here is an example call:

    String s = "sbsncjss"; 
    // longest subsequence length is 5 and longest substring length is 3
    System.out.println("Ans is "   lp(s, 0, s.length() - 1, 0));

CodePudding user response：

How can I modify the code to get longest palindromic substring length

You then need to exclude the cases where characters are skipped. When your code is about to skip a character, the search can continue, but with ans reset to 0.

So:

public static int lp(String str, int i, int j, int ans) {
    if (i == str.length() || j <= 0)
        return ans;

    if (i > j)
        return ans;

    if (i == j)
        return ans   1;

    if (str.charAt(i) == str.charAt(j)) {
        int a = lp(str, i   1, j, 0);   // <-- reset!
        int b = lp(str, i, j - 1, 0);   // <-- reset!
        int c = lp(str, i   1, j - 1, ans   2);
        ans = Math.max(Math.max(a, b), c);
        return ans;
    } else {
        int a = lp(str, i   1, j, 0);   // <-- reset!
        int b = lp(str, i, j - 1, 0);   // <-- reset!
        ans = Math.max(a, b);
        return ans;
    }
}

Be aware that although this works, there are more efficient algorithms for finding the longest palindrome substring. But they are completely different from the algorithm you presented for the longest palindrome subsequence, so it would not be a matter of just making some changes.