Problem
A string is said to be a child of a another string if it can be formed by deleting 0 or more characters from the other string. Letters cannot be rearranged. Given two strings p and q of equal length, what’s the longest string that can be constructed such that it is a child of both?
Input
There are two lines, each with a string, p and q.
Output
the length of the longest string which is a common child of the input strings
Constraints
- 1 <= |size of strings| ≤ 5000
- All characters in string p and q are upper case in the range ascii[A-Z]
Sample Input
PRINT PANEL
Sample Output
2
Solution
Approach: Dynamic Programming
The idea is to use the dynamic programming algorithm which is used to find the Longest Common Subsequence (LCS) in two strings. LCS solution is discussed in this post.
Code Implementation
//
// main.cpp
// Common Child
//
// Created by Himanshu on 21/03/22.
//
#include<iostream>
#include<cmath>
#include<string>
#define MAX_SIZE 5001
using namespace std;
long int lcs[MAX_SIZE][MAX_SIZE] = {0};
long int solve (string p, string q, long int n) {
long int ans = 0;
for (int i=0; i<=n; i++) {
for (int j=0; j<=n; j++) {
if (i == 0 || j == 0) {
lcs[i][j] = 0;
} else if (p[i-1] == q[j-1]) {
lcs[i][j] = lcs[i-1][j-1] + 1;
} else if (p[i-1] != q[j-1]) {
lcs[i][j] = max(lcs[i-1][j], lcs[i][j-1]);
}
if (lcs[i][j] > ans) {
ans = lcs[i][j];
}
}
}
return ans;
}
int main() {
string p, q;
long int n;
cin>>p>>q;
n = p.size();
cout<<solve(p, q, n)<<endl;
return 0;
}
Time complexity: O(n2)
Space complexity: O(n2)