Added DP solution for longest palindromic subsequence.

anxious-coder-lhs · anxious-coder-lhs · commit 9e67e3a74c33 · 2020-10-17T15:15:15.000+05:30
diff --git a/README.md b/README.md
@@ -156,7 +156,8 @@ Happy to accept any contributions to this in any langugage.
    * MaximumRibbonCut_2.ts)
 9. Find Longest Palindromic Subsequence
    * [Solution Brute Force](./dynamic_programming/LongestPalindromicSubsequence_1.ts)
-
+   * [Solution DP Top Down](./dynamic_programming/LongestPalindromicSubsequence_2.ts)
+   * [Solution DP Bottoms Up](./dynamic_programming/LongestPalindromicSubsequence_3.ts)
 
 # TODO Items (More topics to explore further)
 * [All TODO Items](./TODO.md)
diff --git a/dynamic_programming/LongestPalindromicSubsequence_2.ts b/dynamic_programming/LongestPalindromicSubsequence_2.ts
@@ -0,0 +1,56 @@
+/**
+ * 
+ * Problem: Given a string of "n" characters, find the longest palindromic subsequence
+ * of the input string. The subsequnce can remove one or more elements from the original
+ * string retaining the original order of the string. This is a very different problem
+ * from finding the longest palindromic substring without the constraint of removing any
+ * elements.
+ * 
+ * Use the brute force to generate all possible subsequences. While in a subsequence,
+ * if the string is already a palindrome from the ends, continue proceeding inwards.
+ * If it is not palindrome from the end, we can continue ignoring one elements from
+ * the left and right to see if we can achieve a palindromic subsequence. while the brute
+ * force exploration happens, we need to cache all the pre-computed results in an
+ * additional DP storage for use.
+ * 
+ * Complexity....
+ * Time: O(n^2) since beg * end is the worst case of computation, rest of the computations
+ * are cached. Space: O(n^2 + n) since in the worst case, we would have all the n^2 positions 
+ * cahced and stored. Additionally, O(n) space would be used for the recursion stack.
+ * 
+ * @param input 
+ */
+function findLongestPalSubseq1(input: string) {
+    return findLongestPalSubseqHelper1(input, 0, input.length - 1);
+}
+
+function findLongestPalSubseqHelper1(input: string, beg: number, end: number, dp: number[][] = []): number {
+
+    dp[beg] = dp[beg] || [];
+
+    if (dp[beg][end] !== undefined)
+        return dp[beg][end];
+
+    if (end < beg) return 0;
+    else if (end === beg) return 1;
+    else if (input[beg] === input[end]) {
+        // Ends are matching, continue inwards.
+        dp[beg][end] = 2 + findLongestPalSubseqHelper1(input, beg + 1, end - 1);
+        return dp[beg][end]
+    }
+
+    // If the ends are not matching, we may try to skip an element from the end, to attempt
+    // to make a palindromic string
+    const maxWithLeftInclusion = findLongestPalSubseqHelper1(input, beg + 1, end);
+    const maxWithRightInclusion = findLongestPalSubseqHelper1(input, beg, end - 1);
+    dp[beg][end] = Math.max(maxWithLeftInclusion, maxWithRightInclusion);
+    return dp[beg][end];
+}
+
+function testLongestPlalindSubseq1(input: string) {
+    console.log(`Longest Palindromic Subsequence for input ${input}: ${findLongestPalSubseq1(input)}`)
+}
+
+testLongestPlalindSubseq1("abdbca")
+testLongestPlalindSubseq1("cddpd")
+testLongestPlalindSubseq1("pqr")
diff --git a/dynamic_programming/LongestPalindromicSubsequence_3.ts b/dynamic_programming/LongestPalindromicSubsequence_3.ts
@@ -0,0 +1,57 @@
+/**
+ * 
+ * Problem: Given a string of "n" characters, find the longest palindromic subsequence
+ * of the input string. The subsequnce can remove one or more elements from the original
+ * string retaining the original order of the string. This is a very different problem
+ * from finding the longest palindromic substring without the constraint of removing any
+ * elements.
+ * 
+ * Bottoms up dynamic programming is solution is used for identifying the max subsequence.
+ * We start by including one character at a time. With each iteration, we include one more
+ * character. Wuth each new character, there are n^2 possible subsequences, we create those
+ * possible subsequences. With each subsequence, we identify the max palindromic length
+ * using earlier computation and preserved results.
+ * 
+ * Complexity....
+ * Time: O(n^2) since we are creating all the possible subsequences 
+ * Space: O(n^2) since in the worst case, we would have to store the results of the entire possible combination.
+ * @param input 
+ */
+function findLongestPalSubseq2(input: string) {
+    return findLongestPalSubseqHelper2(input);
+}
+
+function findLongestPalSubseqHelper2(input: string): number {
+
+    const dp: number[][] = Array.from({length: input.length}, () => Array(input.length).fill(0));
+    for (let idx = 0; idx < input.length; idx++)
+        dp[idx][idx] = 1;
+
+    /**
+     * DP table is built by including one additional position at each step.
+     * We start from right to left, in order to use the DP formulation function.
+     * At each character that is included, we need to consider its pair of subsequences
+     * with all the other positions/characters identified before.
+     */
+    for (let beg = input.length - 1; beg >= 0; beg--) {
+        for (let end = beg + 1; end < input.length; end++) {
+            if (input[beg] === input[end]) {
+                // If the perfect palindrome is created from the end, we squeeze.
+                dp[beg][end] = dp[beg + 1][end - 1] + 2;
+            } else {
+                // If not, we see the max possible from either left or right.
+                dp[beg][end] = Math.max(dp[beg + 1][end], dp[beg][end - 1]);
+            }
+        }
+    }
+
+    return dp[0][input.length - 1];
+}
+
+function testLongestPlalindSubseq2(input: string) {
+    console.log(`Longest Palindromic Subsequence for input ${input}: ${findLongestPalSubseq2(input)}`)
+}
+
+testLongestPlalindSubseq2("abdbca")
+testLongestPlalindSubseq2("cddpd")
+testLongestPlalindSubseq2("pqr")
