# String Manipulation | Common Child

In this blog we are discussing a problem about string manipulation from Hackerrank. 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. Given two strings of equal length, what's the longest string that can be constructed such that it is a child of both? For example, ABCD and ABDC have two children with maximum length 3, ABC and ABD. They can be formed by eliminating either the D or C from both strings. Note that we will not consider ABCD as a common child because we can't rearrange characters and ABCD != ABDC. Function Description:

Complete the commonChild function in the editor below. It should return the longest string which is a common child of the input strings.

commonChild has the following parameter(s): s1, s2 : two equal length strings Input Format:

There is one line with two space-separated strings, s1 and s2. Constraints: 1 <= | s1 |, | s2 | <= 5000 All characters are upper case in the range ASCII[A-Z]. Output Format:

Print the length of the longest string s, such that s is a child of both s1 and s2. Sample Input: HARRY

SALLY Sample Output: 2 Explanation

The longest string that can be formed by deleting zero or more characters from HARRY and SALLY is AY , whose length is 2. Sample Input 1: AA

BB Sample Output 1: 0 Explanation 1:

AA and BB have no characters in common and hence the output is 0. Sample Input 2: SHINCHAN

NOHARAAA Sample Output 2: 3 Explanation 2:

The longest string that can be formed between SHINCHAN and NOHARAAA while maintaining the order is NHA. Sample Input 3: ABCDEF

FBDAMN Sample Output 3: 2 Explanation 3:

BD is the longest child of the given strings. Implementation using Java: import java.io.*;

import java.math.*;

import java.util.*;

public class Solution {

static int commonChild(String s1, String s2) {

int l1 = s1.length();

int l2 = s2.length();

int count = 0;

int[][] arr = new int[5005][5005];

for (int i = 0; i<l1; i++)

{

for(int j = 0; j<l2; j++)

{

if(s1.charAt(i) == s2.charAt(j))

{

arr[i+1][j+1] = arr[i][j] + 1;

}

else

{

arr[i+1][j+1] = Math.max(arr[i][j+1], arr[i+1][j]);

}

}

}

return arr[l1][l2];

}

private static final Scanner scanner = new Scanner(System.in);

public static void main(String[] args) throws IOException {

String s1 = scanner.nextLine();

String s2 = scanner.nextLine();

int result = commonChild(s1, s2);

System.out.println(result);

scanner.close();

}

} Happy Coding! Follow us on Instagram @programmersdoor Join us on Telegram @programmersdoor Please write comments if you find any bug in above code/algorithm, or find other ways to solve the same problem. Follow Programmers Door for more. #blog #interview #placement #learn #computer #science