Algorithms for Coding Interviews in Python/

...

/

Solution: Longest Palindromic Subsequence

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

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 O(2n)O(2^n), where n is the length of the input sequence. The space complexity is O(n)O(n), which is the maximum number of times that the function is called, so, this is the space used to store the recursion stack.

Solution 2: memoization

def longest_palindromic_subsequence_recursive(lookup_table, s, start_index, end_index):
    """
    Finds the longest palindromic subsequence length
    :param lookup_table: Lookup Table
    :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
    if lookup_table[start_index][end_index] == 0:
        # case 1: elements at the beginning and the end are the same
        if s[start_index] == s[end_index]:
            lookup_table[start_index][end_index] = 2 + longest_palindromic_subsequence_recursive(lookup_table, s, start_index + 1, end_index - 1)
        else:
            # case 2: skip one element either from the beginning or the end
            c1 = longest_palindromic_subsequence_recursive(lookup_table, s, start_index + 1, end_index)
            c2 = longest_palindromic_subsequence_recursive(lookup_table, s, start_index, end_index - 1)
            lookup_table[start_index][end_index] = max(c1, c2)
    return lookup_table[start_index][end_index]
def longest_palindromic_subsequence(s):
    """
    Finds the longest palindromic subsequence length
    :param s: Input string
    :return: Length of longest palindromic subsequence
    """
    # Initializing a lookup table of dimensions len(s) x len(s)
    lookup_table = [[0 for x in range(len(s))] for x in range(len(s))]
    return longest_palindromic_subsequence_recursive(lookup_table, 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

As done in memoization, we use an array, lookup_table, to store the values of the previously solved subproblems.

The two varying values in ...