String Manipulation | Common Child

In this blog we are discussing a problem about string manipulation from Hackerrank.


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.


  • 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:


Sample Output:


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:


Sample Output 1:


Explanation 1: AA and BB have no characters in common and hence the output is 0.

Sample Input 2:


Sample Output 2:


Explanation 2: The longest string that can be formed between SHINCHAN and NOHARAAA while maintaining the order is NHA.

Sample Input 3:


Sample Output 3:


Explanation 3: BD is the longest child of the given strings.

Implementation using Java:

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;
                    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(;

    public static void main(String[] args) throws IOException {
        String s1 = scanner.nextLine();

        String s2 = scanner.nextLine();

        int result = commonChild(s1, s2);


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

12 views0 comments

Recent Posts

See All

        Contact Us

  • LinkedIn
  • Facebook
  • Instagram

©2023 by Programmers Door