Solution: Longest Palindromic Subsequence

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"))