Special Palindrome

Given a String S and a character C, find the length of the longest palindromic subsequence of S containing the character C.

Example:

Input:  char ='a', str="dcbabcd"
Output: 7

Approach

Java

import java.util.Arrays;

public class SpecialPalindrome {
    public static char[] arr;
    public static char c;
    public static int[][] dp = new int[1000][1000];
    public static int[][] dp2 = new int[1000][1000];

    public static void main(String args[]) throws Exception {
        c = 'a';
        arr = "dcbabcd".toCharArray();
        for (int[] a : dp)
            Arrays.fill(a, 0, arr.length, -1);
        for (int[] a : dp2)
            Arrays.fill(a, 0, arr.length, -1);
        lps(0, arr.length - 1);
        int x = solve(0, arr.length - 1);
        System.out.println(x);
    }

    public static int solve(int l, int r) {
        if (l > r)
            return 0;
        if (dp[l][r] != -1)
            return dp[l][r];
        if (l == r)
            return dp[l][r] = (arr[l] == c) ? 1 : 0;
        if (arr[l] != arr[r])
            return dp[l][r] = Math.max(solve(l, r - 1), solve(l + 1, r));
        if (arr[l] == c)
            return dp[l][r] = 2 + lps(l + 1, r - 1);
        return dp[l][r] = (solve(l + 1, r - 1) != 0) ? (solve(l + 1, r - 1) + 2) : 0;

    }

    public static int lps(int l, int r) {
        if (l > r)
            return 0;
        if (dp2[l][r] != -1)
            return dp2[l][r];
        if (l == r)
            return dp2[l][r] = 1;
        if (arr[l] == arr[r])
            return dp2[l][r] = 2 + lps(l + 1, r - 1);
        return dp2[l][r] = Math.max(lps(l, r - 1), lps(l + 1, r));
    }
}