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

        Contact Us

programmersdoor@gmail.com

  • LinkedIn
  • Facebook
  • Instagram

©2023 by Programmers Door