27. Minimum Deletions
The problem can be found at the following link: Question Link
My Approach
Usually, to see if a string is a palindrome, we compare the given string with its reverse. Similarly, we look at the Longest Common Subsequence between the original string and its reverse to find the minimum deletions needed to make a string a palindrome. So, the minimum deletions required are the difference between the string's length and the LCS length.
To do this, we follow these steps:
We use recursion and memoization to compute the Longest Common Subsequence (LCS) of the string and its reverse.
Define a function
lcs
that takes two stringsS
andrevS
, two integersi
andj
, and a 2D vectordp
.Check if either
i
orj
is -1. If true, return 0 as base cases.Check if
dp[i][j]
is not computed (dp[i][j] != -1
). If it's computed, returndp[i][j]
.Check if
S[i]
equalsrevS[j]
. If true, computedp[i][j]
as1 + lcs(S, revS, i - 1, j - 1, dp)
as we find one common character and add it for further steps.If
S[i]
andrevS[j]
are different, compute two values:checkS
aslcs(S, revS, i - 1, j, dp)
.checkRevS
aslcs(S, revS, i, j - 1, dp)
.return the
dp[i][j]
as the maximum ofcheckS
andcheckRevS
.
The minimum number of deletions required is determined by the difference between the string's length and the length of the LCS.
Time and Auxiliary Space Complexity
Time Complexity:
O(N^2)
, whereN
is the length of the input stringS
. This is because we use dynamic programming to calculate the LCS.Auxiliary Space Complexity:
O(N^2)
, as we use a 2D DP array to store intermediate results.
Code (C++)
Contribution and Support
For discussions, questions, or doubts related to this solution, please visit our discussion section. We welcome your input and aim to foster a collaborative learning environment.
If you find this solution helpful, consider supporting us by giving a ⭐ star to the getlost01/gfg-potd repository.
Last updated