Common Child | Algorithms | HackerRank Solution [Medium]

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?

HackerRank Problem Link

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.

//
//  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)

Leave a Reply

Your email address will not be published.