In this post i am going to discuss problems that you can solve using LCS. Recently i solved question about DP on string and i think there are more problems that you can solve only using LCS with a little bit of change.
- If you know what LCS is thats great because i'm going to explain how you can use the same code in different problems
- If you don't know here is the brief explanation regarding LCS (Longest Common Subsequence)
1143. Longest Common Subsequence
A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.
Example :
Input: text1 = "abcdgh", text2 = "abedfhq"
Output: 4
Explanation: The longest common subsequence is "abdh" and its length is 4.here is the pseudo code for that
int LCS(string s, string t, int n, int m)
{
// n = length of s
// m = length of t
//Base condition
if(n==0 || m == 0)
return 0;
if(s[n-1] == t[m-1])
return 1 + LCS(s,t,n-1,m-1)
else
return max(LCS(s,t,n,m-1), LCS(s,t,n-1,m))Let's understand Base case:
As s[n] != t[m]
- We will make a call to LCS(s,t,0-1,1), i.e LCS(-1,1) but a negative index simply means that there are no more indexes to be explored, so we simply return 0. Same is the case when s[n] == t[m]
and if s[n] != t[m]
- Two separate calls are made: one with LCS(s,t,n,m-1) (shrinking only t) and another with LCS(s,t,n-1,m) (shrinking only s).
- This prevents the loss of potential characters in the common subsequence by exploring both cases thoroughly, and the algorithm returns the maximum result from these calls.
HERE IS THE TABULATION CODE (i'm going to use this in all sol)
int longestCommonSubsequence(string text1, string text2) {
int n = text1.size();
int m = text2.size();
vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (text1[i - 1] == text2[j - 1]) {
dp[i][j] = 1 + dp[i - 1][j - 1];
} else
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
return dp[n][m];
}Let's get down to business
if you solve Longest Common subsequence. you can pretty much solve Longest common substring.
Although it is not on the leetcode but here is the similar problem
718. Maximum Length of Repeated Subarray
Given two integer arrays nums1 and nums2, return the maximum length of a subarray that appears in both arrays.
Example :
Input: nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
Output: 3
Explanation: The repeated subarray with maximum length is [3,2,1].can you find the pattern ??
-
if(nums1[i-1] != nums2[j-1]),
the characters don’t match, therefore the consecutiveness of characters is broken. So we set the cell value (dp[i][j]) as 0. -
if (nums1[i-1] == nums2[j-1])matches weset its value to 1+dp[i-1][j-1]
we have to keep track of maximum length encounter because answer is max(dp[i][j])
int findLength(vector<int>& nums1, vector<int>& nums2) {
int n = nums1.size();
int m = nums2.size();
vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
int ans = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (nums1[i - 1] == nums2[j - 1]) {
dp[i][j] = 1 + dp[i - 1][j - 1];
ans = max(ans, dp[i][j]);
} else
dp[i][j] = 0;
}
}
return ans;
}516. Longest Palindromic Subsequence
Given a string s, find the longest palindromic subsequence's length in s.
A palindromic string is a string that is equal to its reverse.
Example :
Input: s = "bbbab"
Output: 4
Explanation: One possible longest palindromic subsequence is "bbbb".Let's rewrite the input
Input: s = "bbbab" t = "babbb"Now can you see it ??
Basically The longest palindromic subsequence of a string is the longest common subsequence of the given string and its reverse.
int longestPalindromeSubseq(string s) {
string a = s;
reverse(a.begin(), a.end());
int n = s.size();
vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (s[i - 1] == a[j - 1])
dp[i][j] = 1 + dp[i - 1][j - 1];
else
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
return dp[n][n];
}/
Below question is not on leetcode.(I solved it on another platform but i didn't remember which one)
Minimum no. of deletions & insertions to transform string a into string b
convert string a into string b. you can do
- delete charcter
- insert charcter
Input: a = "heap" b = "pea"
Output: deletion : 2 insertion : 1for above example first we have to delete h and p from a so we have "ea" and then we can insert p to achive our string b.
-
can you find pattern??
see "ea" is what?? ----------> LCS
a = "heap" b = "pea" -
minimum number of deletions = a.length – LCS
-
minimum number of Insertions minInsert = b.length – LCS
vector<pair> MinDelAndIns(string a, string b)
{
int n = a.length();
int m = b.length();
int LCS_length = LCS(a,b,n,m)
int delete = LCS - n;
int insert = LCS - m;
return {delete,insert}
}Now You can solve
72. Edit Distance
In this question you also can replace charcter.
- This is little bit different from LCS THUS i'm not gonna write down the solution but if you understand all the above discussion you can do it by yourself. Just spend some time and then it clicks you.
1312. Minimum Insertion Steps to Make a String Palindrome
Given a string s. In one step you can insert any character at any index of the string.
Return the minimum number of steps to make s palindrome.
Input: s = "mbadm"
Output: 2
Explanation: String can be "mbdadbm" or "mdbabdm".Let's think it as before where we solve longest palindrome subsequence
Input: s = "mbadm" t = "mdabm"
Output: 2
Explanation: String can be "mbdadbm" or "mdbabdm".- As we can see LCS is "mam" .
- what we don't have is "b" and "d" in opposite side to make it palindrome we can add those two charcter.
- so basically our answer would be length of string - LCS length
int minInsertions(string s) {
string st = s;
int n = s.size();
reverse(st.begin(), st.end());
vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (s[i - 1] == st[j - 1])
dp[i][j] = 1 + dp[i - 1][j - 1];
else
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
return n - dp[n][n];
}Now if interviwer ask you what is the minimum number of deletion to make it a palindrom.
- can you answer it??
- In above question what we did was add two charcter on opposite side but we can also delete it right??
it also give us palindrome
number of insertion = number of deletion
392. Is Subsequence
Given two strings s and t, return true if s is a subsequence of t, or false otherwise.
Example :
Input: s = "abc", t = "ahbgdc"
Output: trueCan you find a pattern??
You can also do this question by two pointer but this post is about LCS So guess what..
- if LCS.length == s.length that does mean that s is present in t right...
bool isSubsequence(string s, string t) {
int n = s.size();
int m = t.size();
vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
int ans = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (s[i - 1] == t[j - 1]) {
dp[i][j] = 1 + dp[i - 1][j - 1];
} else
dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
}
}
return dp[n][m] == n;
}583. Delete Operation for Two Strings
** Example : **
Input: word1 = "sea", word2 = "eat"
Output: 2
Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".- It is straight forward from the explanation....
- we just have to subtract the length of LCS from individual string length..
int minDistance(string word1, string word2) {
int n = word1.size();
int m = word2.size();
vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (word1[i - 1] == word2[j - 1])
dp[i][j] = 1 + dp[i - 1][j - 1];
else
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
return (n - dp[n][m]) + (m - dp[n][m]);
}1092. Shortest Common Supersequence
Given two strings str1 and str2, return the shortest string that has both str1 and str2 as subsequences. If there are multiple valid strings, return any of them.
A string s is a subsequence of string t if deleting some number of characters from t (possibly 0) results in the string s.
I KNOW this question is in hard category but it can be asked as medium if they say you only have to give length of the shortest common supersequence.
Example :
Input: str1 = "abac", str2 = "cab"
Output: "cabac"
Explanation:
str1 = "abac" is a subsequence of "cabac" because we can delete the first "c".
str2 = "cab" is a subsequence of "cabac" because we can delete the last "ac".
The answer provided is the shortest such string that satisfies these properties.let's for simplacity we take simple example
Input: str1 = "leet", str2 = "ete"
Output: "leete"Can you use LCS here??
we have LCS in our answer as substring if you carefully notice..
"leete"
"cabac"
for answer of length part don't you think it is same as we did before.
let just say we add two string as it is "leetete" In this case we have our LCS 2 times and we want shortest length as our answer.
can we make a string such that LCS is there only one time and then we can add all remaining charcter from strings such that order is maintained.
Let's first find length of shortest common supersequence
ans = LCS + (A - LCS) + (B-LCS)
= A + B - LCS
string shortestCommonSupersequence(string str1, string str2) {
int n = str1.size();
int m = str2.size();
vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (str1[i - 1] == str2[j - 1]) {
dp[i][j] = 1 + dp[i - 1][j - 1];
} else
dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
}
}
return n + m - dp[n][m];For printing shortest common supersequence you have to understand how to print LCS
Printing LCS ( You can find this quetion on other platforms)
This question is not on leetcode ( i didn't find it) but if it were than it would be in hard category..
For printing LCS we require our top-down table..
Example:
-
In the reconstruction process of the Longest Common Substring, each cell is examined. If the characters at positions i-1 and j-1 are equal, the character is added to the substring, and indices shift diagonally (↖).
-
If not, the algorithm moves to the cell with the larger value either to the left (←) or above (↑).
-
This continues until either i or j becomes non-positive, yielding the reconstructed Longest Common Substring.
string PrintLCS(string s, string t)
{
// LCS TABLE IS BUILT.
int i = n, j = m;
string ans = "";
while(i > 0 && j > 0)
{
if(s1[i-1] == s2[j-1])
{
ans.push_back(s1[i-1]);
i--;
j--;
}
else
{
if(dp[i][j-1] > dp[i-1][j])
{
j--;
}
else
i--;
}
}
// we have to reverse it because we did our traversal backwards so string is in reverse order.
reverse(ans.begin(), ans.end());
return ans;
}1092. Shortest Common Supersequence
NOW Let's move back to our Question..
- At each cell, the algorithm checks if characters at positions i-1 (str1) and j-1 (str2) are equal. If true, the character is added to the result string (ans), and indices move diagonally (↖).
- If not, the larger-valued cell (← or ↑) determines the next move and we have to add that charcter
- The process continues until either i or j becomes non-positive.
- After breaking, if i > 0, remaining characters from str1 are appended to ans; if j > 0, remaining characters from str2 are added. This ensures all characters contribute to the Longest Common Subsequence.
string shortestCommonSupersequence(string str1, string str2)
{
//OUR LCS TABLE IS BUILT.
string ans = "";
int i = n, j = m;
while(i > 0 && j > 0)
{
if(str1[i-1] == str2[j-1])
{
ans.push_back(str1[i-1]);
i--;
j--;
}
else
{
if(dp[i-1][j] > dp[i][j-1])
{
ans.push_back(str1[i-1]);
i--;
}
else
{
ans.push_back(str2[j-1]);
j--;
}
}
}
while(i > 0)
{
ans += str1[i-1];
i--;
}
while(j > 0)
{
ans += str2[j-1];
j--;
}
reverse(ans.begin(), ans.end());
return ans;
}Longest Repeating Subsequence
You are given a string s of length n.. You are tasked to find the longest subsequence repeated in string s.
- There is only one extra condition everything else is same.
- when both charcter are same
int LRS(string text1)
{
string text2 = text1;
int n = text1.size();
int m = text2.size();
vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (text1[i - 1] == text2[j - 1] && i != j ) {
dp[i][j] = 1 + dp[i - 1][j - 1];
} else
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
return dp[n][m];
}Hope this will help you a bit to ace your next coding interviews or competitive programming contest.
"Success is not final, failure is not fatal: It is the courage to continue that counts." - Winston Churchill
Any suggestions on improving Post are appreciated.
if you know similar question on this topic then comment.