Add files via upload

DARKcoder37 · web-flow · commit fd7eb8252222 · 2023-04-14T21:12:03.000+05:30
diff --git a/Daily Challenge/516. Longest Palindromic Subsequence/README.md b/Daily Challenge/516. Longest Palindromic Subsequence/README.md
@@ -0,0 +1,24 @@
+516. Longest Palindromic Subsequence(Medium)
+
+Given a string s, find the longest palindromic subsequence's length in s.
+
+A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.
+
+ 
+
+Example 1:
+
+Input: s = "bbbab"
+Output: 4
+Explanation: One possible longest palindromic subsequence is "bbbb".
+Example 2:
+
+Input: s = "cbbd"
+Output: 2
+Explanation: One possible longest palindromic subsequence is "bb".
+ 
+
+Constraints:
+
+1 <= s.length <= 1000
+s consists only of lowercase English letters.
diff --git a/Daily Challenge/516. Longest Palindromic Subsequence/sol.py b/Daily Challenge/516. Longest Palindromic Subsequence/sol.py
@@ -0,0 +1,37 @@
+# 1) Top down
+
+class Solution:
+  def longestPalindromeSubseq(self, s: str) -> int:
+    # dp(i, j) := LPS's length in s[i..j]
+    @functools.lru_cache(None)
+    def dp(i: int, j: int) -> int:
+      if i > j:
+        return 0
+      if i == j:
+        return 1
+      if s[i] == s[j]:
+        return 2 + dp(i + 1, j - 1)
+      return max(dp(i + 1, j), dp(i, j - 1))
+
+    return dp(0, len(s) - 1)
+
+# 2) Bottom up
+
+class Solution:
+  def longestPalindromeSubseq(self, s: str) -> int:
+    n = len(s)
+    # dp[i][j] := LPS's length in s[i..j]
+    dp = [[0] * n for _ in range(n)]
+
+    for i in range(n):
+      dp[i][i] = 1
+
+    for d in range(1, n):
+      for i in range(n - d):
+        j = i + d
+        if s[i] == s[j]:
+          dp[i][j] = 2 + dp[i + 1][j - 1]
+        else:
+          dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
+
+    return dp[0][n - 1]
