Added DP and BF solutions for longest palindromic substring.

anxious-coder-lhs · anxious-coder-lhs · commit 667faa5d8a00 · 2020-10-18T20:34:34.000+05:30
diff --git a/README.md b/README.md
@@ -158,6 +158,11 @@ Happy to accept any contributions to this in any langugage.
    * [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)
+10. Find Longest Palindromic Substring
+   * [Solution Brute Force](./dynamic_programming/LongestPalindromicSubstring_1.ts)
+   * [Solution BF Recursive](./dynamic_programming/LongestPalindromicSubstring_2.ts)
+   * [Solution DP Top Down](./dynamic_programming/LongestPalindromicSubstring_4.ts)
+   * [Solution DP Bottom Up](./dynamic_programming/LongestPalindromicSubstring_3.ts)
 
 # TODO Items (More topics to explore further)
 * [All TODO Items](./TODO.md)
diff --git a/dynamic_programming/LongestPalindromicSubstring_1.ts b/dynamic_programming/LongestPalindromicSubstring_1.ts
@@ -0,0 +1,46 @@
+/**
+ * Problem: Longest Palindromic Substring.
+ * Given a string, find the longest possible palindromic substring of the string. The
+ * substring should be of the exact order without skipping any elements in between.
+ * 
+ * Solution: Solution is based on simple brute force. We create the boundary pairs of
+ * the substring using a quadratic loop. For each substring boundary conditions, we invoke
+ * the check for is palindrome which does an iteraction of O(n) to validate if the string
+ * is palindrome.
+ * 
+ * Complexity...
+ * Time: O(n^3) since the elements are iterated in 3 nested levels.
+ * Space: O(1) since no other additional space is used.
+ * 
+ * @param input 
+ */
+function findLongestPalindromicSubstring1(input: string) {
+    let maxLength = 0;
+    for (let beg = 0; beg < input.length; beg++) {
+        for(let end = beg; end < input.length; end++) {
+            if (isPalindrome1(input, beg, end)) {
+                maxLength = Math.max(maxLength,end - beg + 1);
+            }
+        }
+    }
+
+    return maxLength;
+}
+
+function isPalindrome1(input: string, beg: number, end: number) {
+    while(beg !== end) {
+        if (input[beg] !== input[end]) return false
+        beg++;
+        end--;
+    }
+
+    return true;
+}
+
+function testLongestPal1(input: string) {
+    console.log(`Longest Palindromic substring length for input: ${input} is ${findLongestPalindromicSubstring1(input)}`);
+}
+
+testLongestPal1("abdbca")
+testLongestPal1("cddpd")
+testLongestPal1("pqr")
diff --git a/dynamic_programming/LongestPalindromicSubstring_2.ts b/dynamic_programming/LongestPalindromicSubstring_2.ts
@@ -0,0 +1,49 @@
+/**
+ * Problem: Longest Palindromic Substring.
+ * Given a string, find the longest possible palindromic substring of the string. The
+ * substring should be of the exact order without skipping any elements in between.
+ * 
+ * Solution: Solution is based on simple brute force. We recursively navigate from two ends to squeeze inside. At each step, we check if the
+ * entire string including the 2 endpoints are palindromes. If the entire string with the 2 ends are not palindromes (which we can compare with
+ * the lengths equality), we may try to squeeze the endpoints. At each level of squeezing we squeeze eihter left or right.
+ * 
+ * Complexity...
+ * Time: O(3^n) since at each character positions, we are expanding the solution space to 3 more childs.
+ * Space: O(n) since at any point of time, recursion stack is at max n.
+ * 
+ * @param input 
+ */
+function findLongestPalindromicSubstring2(input: string) {
+    return findLongestPalSubseqHelper2(input, 0, input.length - 1);
+}
+
+function findLongestPalSubseqHelper2(input: string, beg: number, end: number) {
+    // Boundary/Base conditions to terminate the loop.
+    if (beg > end) return 0;
+    if (beg === end) return 1;
+
+    // Recursive palindromic checks.
+    if (input[beg] === input[end]) {
+        // If the 2 endpoints are equal, we may attempt to recursively check the palindrome.
+        const maxWithInclusion = 2 + findLongestPalSubseqHelper2(input, beg + 1, end - 1);
+        
+        // Since, we must include adjacent chars and cannot skip from either side at each level, we should validate
+        // the length.
+        if (maxWithInclusion === end - beg + 1) {
+            return maxWithInclusion;
+        }
+    }
+    
+    // If the 2 ends are not equal, we may try to check substring with beg or end only.
+    const maxWithExclusion1 = findLongestPalSubseqHelper2(input, beg, end - 1);
+    const maxWithExclusion2 = findLongestPalSubseqHelper2(input, beg + 1, end);
+    return Math.max(maxWithExclusion1, maxWithExclusion2);
+}
+
+function testLongestPal2(input: string) {
+    console.log(`Longest Palindromic substring length for input: ${input} is ${findLongestPalindromicSubstring2(input)}`);
+}
+
+testLongestPal2("abdbca")
+testLongestPal2("cddpd")
+testLongestPal2("pqr")
diff --git a/dynamic_programming/LongestPalindromicSubstring_3.ts b/dynamic_programming/LongestPalindromicSubstring_3.ts
@@ -0,0 +1,46 @@
+/**
+ * Problem: Longest Palindromic Substring.
+ * Given a string, find the longest possible palindromic substring of the string. The
+ * substring should be of the exact order without skipping any elements in between.
+ * 
+ * Solution: DP solution uses the bottom up solution to identify the longest palindromic substring with one
+ * character at a time. With each new character added, we validate if it makes the entire string palindrome from
+ * end to end. We do that in O(1) time operation by comparing the ends and comparing the substring excluding the ends.
+ * On the other side, if the entire string is not palindrome, we check if any of the 2 ends can be skipped to have
+ * a perfect palindrome. The entire sequence is repeated till we add each character.
+ * 
+ * Complexity...
+ * Time: O(n^2) since the elements are iterated in 2 nested levels.
+ * Space: O(n^2) since entire substring ends combination is saved, althought it can be reduced to O(n).
+ * 
+ * @param input 
+ */
+function findLongestPalindromicSubstring3(input: string) {
+
+    // New DP table for caching.
+    const dp: number[][] = Array.from({length: input.length + 1}, () => Array(input.length).fill(0));
+
+    // Initialize the DP table for boundary conditions
+    for (let idx = 0; idx < input.length; idx++) dp[idx][idx] = 1;
+
+    // Build the entire table
+    for (let beg = input.length - 1; beg >= 0; beg--) {
+        for (let end = beg + 1; end < input.length; end++) {
+            if (input[beg] === input[end] && dp[beg + 1][end - 1] + 2 === end - beg + 1) {
+                dp[beg][end] = 2 + dp[beg + 1][end - 1];
+            } else {
+                dp[beg][end] = Math.max(dp[beg + 1][end], dp[beg][end - 1]);
+            }
+        }
+    }
+
+    return dp[0][input.length - 1];
+}
+
+function testLongestPal3(input: string) {
+    console.log(`Longest Palindromic substring length for input: ${input} is ${findLongestPalindromicSubstring3(input)}`);
+}
+
+testLongestPal3("abdbca")
+testLongestPal3("cddpd")
+testLongestPal3("pqr")
diff --git a/dynamic_programming/LongestPalindromicSubstring_4.ts b/dynamic_programming/LongestPalindromicSubstring_4.ts
@@ -0,0 +1,57 @@
+/**
+ * Problem: Longest Palindromic Substring.
+ * Given a string, find the longest possible palindromic substring of the string. The
+ * substring should be of the exact order without skipping any elements in between.
+ * 
+ * Solution: Solution is based on simple brute force. We recursively navigate from two ends to squeeze inside. At each step, we check if the
+ * entire string including the 2 endpoints are palindromes. If the entire string with the 2 ends are not palindromes (which we can compare with
+ * the lengths equality), we may try to squeeze the endpoints. At each level of squeezing we squeeze eihter left or right.
+ * 
+ * Adds DP table for caching previous saved results.
+ * 
+ * Complexity...
+ * Time: O(3^n) since at each character positions, we are expanding the solution space to 3 more childs.
+ * Space: O(n) since at any point of time, recursion stack is at max n.
+ * 
+ * @param input 
+ */
+function findLongestPalindromicSubstring4(input: string) {
+    return findLongestPalSubseqHelper4(input, 0, input.length - 1, Array.from({length: input.length}, () => Array(input.length)));
+}
+
+function findLongestPalSubseqHelper4(input: string, beg: number, end: number, dp: number[][]) {
+    // Boundary/Base conditions to terminate the loop.
+    if (beg > end) return 0;
+    if (beg === end) return 1;
+
+    // Check if the results are already cached.
+    if (dp[beg][end] !== undefined) {
+        return dp[beg][end];
+    }
+
+    // Recursive palindromic checks.
+    if (input[beg] === input[end]) {
+        // If the 2 endpoints are equal, we may attempt to recursively check the palindrome.
+        const maxWithInclusion = 2 + findLongestPalSubseqHelper4(input, beg + 1, end - 1, dp);
+        
+        // Since, we must include adjacent chars and cannot skip from either side at each level, we should validate
+        // the length.
+        if (maxWithInclusion === end - beg + 1) {
+            return maxWithInclusion;
+        }
+    }
+    
+    // If the 2 ends are not equal, we may try to check substring with beg or end only.
+    const maxWithExclusion1 = findLongestPalSubseqHelper4(input, beg, end - 1, dp);
+    const maxWithExclusion2 = findLongestPalSubseqHelper4(input, beg + 1, end, dp);
+    dp[beg][end] =  Math.max(maxWithExclusion1, maxWithExclusion2);
+    return dp[beg][end]
+}
+
+function testLongestPal4(input: string) {
+    console.log(`Longest Palindromic substring length for input: ${input} is ${findLongestPalindromicSubstring4(input)}`);
+}
+
+testLongestPal4("abdbca")
+testLongestPal4("cddpd")
+testLongestPal4("pqr")
