Search⌘ K
AI Features
Home
Courses
Algorithms for Coding Interviews in Python

Solution: Longest Palindromic Subsequence

This review provides a detailed analysis of the different ways to solve the longest palindromic subsequence problem.

We'll cover the following...

Solution 1: brute force

Python 3.5
def longest_palindromic_subsequence_recursive(s, start_index, end_index):
    """
    Finds the longest palindromic subsequence length
    :param s: Input string
    :param start_index: Starting index of the sequence
    :param end_index: Ending index of the sequence
    :return: Length of longest palindromic subsequence
    """
    if start_index > end_index:
        return 0
    # Every sequence with one element is a palindrome of length 1
    if start_index == end_index:
        return 1
    # Case 1: elements at the beginning and the end are the same
    if s[start_index] == s[end_index]:
        return 2 + longest_palindromic_subsequence_recursive(s, start_index + 1, end_index - 1)
    # Case 2: skip one element either from the beginning or the end
    c1 = longest_palindromic_subsequence_recursive(s, start_index + 1, end_index)
    c2 = longest_palindromic_subsequence_recursive(s, start_index, end_index - 1)
    return max(c1, c2)
def longest_palindromic_subsequence(s):
    """
    Finds the longest palindromic subsequence length
    :param s: Input string
    :return: Length of longest palindromic subsequence
    """
    return longest_palindromic_subsequence_recursive(s, 0, len(s) - 1)
# Driver code to test the above function
if __name__ == '__main__':
    print(longest_palindromic_subsequence("cddpd"))
    print(longest_palindromic_subsequence("abdbca"))
    print(longest_palindromic_subsequence("cddpd"))
    print(longest_palindromic_subsequence("pqr"))

Explanation

By now, you must have noticed a pattern in the way we approach dynamic programming problems.

In this brute force solution,

  1. If the element at the beginning and the end are the same, we increase our count by two and make a recursive call for the remaining sequence (line 17 and 18)
  2. Otherwise, we skip the element either from the beginning or the end to make two recursive calls for the remaining subsequence. After that, we return the greater result (line 21 and 22)

Time complexity

The time complexity of the above algorithm is exponential ...