Skip to content

Commit c031f7f

Browse files
anxious-coder-lhsanxious-coder-lhs
committed
Added solution for longest palindromic subsequence brute force.
1 parent d2b2623 commit c031f7f

File tree

3 files changed

+61
-4
lines changed

3 files changed

+61
-4
lines changed

‎README.md

Lines changed: 5 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -114,7 +114,7 @@ Happy to accept any contributions to this in any langugage.
114114
* [Solution Brute Force](./dynamic_programming/01KnapsackProblem_1.ts)
115115
* [Solution Dynamic Programming Top Down](./dynamic_programming/01KnapsackProblem_2.ts)
116116
* [Solution Dynamic Programming Bottoms Up](./dynamic_programming/01KnapsackProblem_3.ts)
117-
* [Solution Dynamic Programming with Chosen Weights](./dynamic_programming/01KnapsackProblem_4.ts)
117+
\ * [Solution Dynamic Programming with Chosen Weights](./dynamic_programming/01KnapsackProblem_4.ts)
118118
* [Solution Optimized Space 1](./dynamic_programming/01KnapsackProblem_5.ts)
119119
* [Solution Optimized Space 2](./dynamic_programming/01KnapsackProblem_6.ts)
120120
2. Equal Subset Problem
@@ -152,7 +152,10 @@ Happy to accept any contributions to this in any langugage.
152152
* [Solution Dynamic Programming Bottoms Up](./dynamic_programming/MinCoinChange_2.ts)
153153
8. Maximum Ribbon Cut
154154
* [Solution Dynamic Programming Top Down](./dynamic_programming/MaximumRibbonCut_1.ts)
155-
* [Solution Dynamic Programming Bottoms Up](./dynamic_programming/MaximumRibbonCut_2.ts)
155+
* [Solution Dynamic Programming Bottoms Up](./dynamic_programming/
156+
* MaximumRibbonCut_2.ts)
157+
9. Find Longest Palindromic Subsequence
158+
* [Solution Brute Force](./dynamic_programming/LongestPalindromicSubsequence_1.ts)
156159

157160

158161
# TODO Items (More topics to explore further)

‎dynamic_programming/LongestPalindromicSubsequence_1.ts

Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,48 @@
1+
/**
2+
*
3+
* Problem: Given a string of "n" characters, find the longest palindromic subsequence
4+
* of the input string. The subsequnce can remove one or more elements from the original
5+
* string retaining the original order of the string. This is a very different problem
6+
* from finding the longest palindromic substring without the constraint of removing any
7+
* elements.
8+
*
9+
* Use the brute force to generate all possible subsequences. While in a subsequence,
10+
* if the string is already a palindrome from the ends, continue proceeding inwards.
11+
* If it is not palindrome from the end, we can continue ignoring one elements from
12+
* the left and right to see if we can achieve a palindromic subsequence.
13+
*
14+
* Complexity....
15+
* Time: O(2^n) since we are making choices for recursion at each step. We choose to
16+
* either ignore an element or to include id.
17+
* Space: O(n) since in the worst case, we would have all the n positions opened to be
18+
* compared.
19+
*
20+
* @param input
21+
*/
22+
function findLongestPalSubseq(input: string) {
23+
return findLongestPalSubseqHelper(input, 0, input.length - 1);
24+
}
25+
26+
function findLongestPalSubseqHelper(input: string, beg: number, end: number): number {
27+
28+
if (end < beg) return 0;
29+
else if (end === beg) return 1;
30+
else if (input[beg] === input[end]) {
31+
// Ends are matching, continue inwards.
32+
return 2 + findLongestPalSubseqHelper(input, beg + 1, end - 1);
33+
}
34+
35+
// If the ends are not matching, we may try to skip an element from the end, to attempt
36+
// to make a palindromic string
37+
const maxWithLeftInclusion = findLongestPalSubseqHelper(input, beg + 1, end);
38+
const maxWithRightInclusion = findLongestPalSubseqHelper(input, beg, end - 1);
39+
return Math.max(maxWithLeftInclusion, maxWithRightInclusion);
40+
}
41+
42+
function testLongestPlalindSubseqBF(input: string) {
43+
console.log(`Longest Palindromic Subsequence for input ${input}: ${findLongestPalSubseq(input)}`)
44+
}
45+
46+
testLongestPlalindSubseqBF("abdbca")
47+
testLongestPlalindSubseqBF("cddpd")
48+
testLongestPlalindSubseqBF("pqr")

‎level_medium/LeetCode_22_Generate_Paranthesis_3.ts

Lines changed: 8 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -4,8 +4,13 @@
44
* checks for the boundary conditions to see if the solution can be found in this path. If the
55
* solution cannot be found, the solution space is backtracked and it is not explored further.
66
*
7+
* Here, we define a function backtrack which keeps track of remaining number of open & closing parenthesis (denoted
8+
* as m and n respectively). If m == n == 0, add the string to answer. If there are open parenthesis left (i.e. m > 0),
9+
* it is possible to append an open parenthesis; if there are more closing parenthesis than open parenthesis (i.e. n >
10+
* m),it is possible to append a closing parenthesis.
11+
*
712
* Complexity: Time and Space O((4^n)/(n^(1/2)).
8-
* Refer https://leetcode.com/problems/generate-parentheses/solution/ for more details.
13+
* Refer https://leetcode.com/problems/generate-parentheses/solution/ for more det
914
*
1015
* @param n
1116
*/
@@ -30,7 +35,8 @@ function genHelper(n: number, result: string[], open: number = 0, close: number
3035

3136
// Boundary condition to validate the backtracking again if required, or we can proceed.
3237
if (open > close) {
33-
// 2nd condition validates if we have not added closing braces before the opening braces.
38+
// We can break the current solution tree if we see that the number of closing braces are equal or greater
39+
// than the opening braces, which makes the string invalid right away.
3440
genHelper(n, result, open, close + 1, str + ")");
3541
}
3642
}

0 commit comments

Comments
 (0)