CODEWITHSUNDEEP
palindromelcslongest-substring
NITESH SHARMA
NITESH SHARMA

Reputation: 21

longest palindromic substring using lcs?

I was solving this longest palindromic substring problem on leetcode and I followed the dynamic programming approach by creating one n*n boolean table(which I guess is also the standard solution to this) and successfully solved it but I was just wondering if this problem can be done using the technique that we use in finding out longest common subsequence or to be more precise, just wish to know whether the LCS problem is parent question of this problem as well like in the case of longest palindromic subsequence which can be solved easily through LCS by taking one another string as reverse of original string.

I searched web but didn't find any solution using LCS technique that's why thought of asking it here. If it is possible to solve using lcs technique then please provide the approach or else some good reason for why it can't be solved using LCS.

Upvotes: 2

Views: 1483

Answers (1)

berlin
berlin

Reputation: 526

I actually solved this exact problem in the exact way you wanted! We can do it in the LCS method using a single array, but the overhead in this is that you will have to check every combination if it is a palindrome manually. See below for the solution by this way. This was accepted on LC as well.

    public String longestPalindrome(String s) {
        int maxlen = 1;
        int len = s.length();
        String[] dp = new String[len];
        dp[0] = s.substring(0,1);
        for (int i = 1; i < len; i++) {
            dp[i] = dp[i-1];
            for (int j = 0; i - j >= maxlen; j++) {
                if (s.charAt(j) != s.charAt(i)) continue;
                if (isPal(s.substring(j, i + 1))) {
                    dp[i] = s.substring(j, i + 1);
                    maxlen = i - j;
                    break;
                }
            }
        }
        return dp[len-1];
    }
    
    public boolean isPal(String s) {
        for (int i = 0; i < s.length()/2; i++) {
            if (s.charAt(i) != s.charAt(s.length()-1-i)) return false;
        }
        return true;
    }

Upvotes: 1

Related Questions