longest_palindromic_subsequence.py

"""
author: Sanket Kittad
Given a string s, find the longest palindromic subsequence's length in s.
Input: s = "bbbab"
Output: 4
Explanation: One possible longest palindromic subsequence is "bbbb".
Leetcode link: https://leetcode.com/problems/longest-palindromic-subsequence/description/
"""


deflongest_palindromic_subsequence(input_string: str) ->int:
"""
 This function returns the longest palindromic subsequence in a string
 >>> longest_palindromic_subsequence("bbbab")
 4
 >>> longest_palindromic_subsequence("bbabcbcab")
 7
 """
n=len(input_string)
rev=input_string[::-1]
m=len(rev)
dp= [[-1] * (m+1) foriinrange(n+1)]
foriinrange(n+1):
dp[i][0] =0
foriinrange(m+1):
dp[0][i] =0

# create and initialise dp array
foriinrange(1, n+1):
forjinrange(1, m+1):
# If characters at i and j are the same
# include them in the palindromic subsequence
ifinput_string[i-1] ==rev[j-1]:
dp[i][j] =1+dp[i-1][j-1]
else:
dp[i][j] =max(dp[i-1][j], dp[i][j-1])

returndp[n][m]


if__name__=="__main__":
importdoctest

doctest.testmod()