Common Child

Problem Statement :

```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  is a child of both s1 and s2.```

Solution :

```                            ```Solution in C :

In  C++ :

#include <cmath>
#include <cstdio>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;

int dp[5005][5005];

int main() {
string a, b;
cin >> a >> b;

for(int i = 0; i < a.size(); ++i)
for(int j = 0; j < b.size(); ++j)
if(a[i] == b[j])
dp[i + 1][j + 1] = dp[i][j] + 1;
else
dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j]);

cout << dp[a.size()][b.size()];
return 0;
}

In   Java ;

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

public static void main(String[] args) {
Scanner s = new Scanner(System.in);
String s1 = s.nextLine();
String s2 = s.nextLine();
int[][] lengths = new int[s1.length()+1][s2.length()+1];

for (int i = 1; i < lengths.length; i++) {
for (int j = 1; j < lengths.length; j++) {
if (s1.charAt(i-1) == s2.charAt(j-1)) {
lengths[i][j] = lengths[i-1][j-1] + 1;
}
else if (lengths[i][j-1] > lengths[i-1][j]) {
lengths[i][j] = lengths[i][j-1];
}
else {
lengths[i][j] = lengths[i-1][j];
}
}
}
System.out.println(lengths[lengths.length-1][lengths.length-1]);
}
}

In  C :

#include<stdio.h>
#include<string.h>
char str1[5005],str2[5005];
int c[5005][5005];
int main()
{
int i,j,m,n;
scanf("%s %s",str1+1,str2+1);
m=strlen(str1+1);
n=strlen(str2+1);
for(i=1;i<=m;i++)c[i][0]=0;
for(j=0;j<=n;j++)c[0][j]=0;
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
{
if(str1[i]==str2[j])
c[i][j]=c[i-1][j-1]+1;
else if(c[i-1][j]>=c[i][j-1])
c[i][j]=c[i-1][j];
else
c[i][j]=c[i][j-1];
}
printf("%d\n",c[m][n]);
return 0;
}

In  Python3 :

def llis(a, b):
m = len(a)
n = len(b)
prev = [0 for x in range(n + 1)]
for i in range(1, m + 1):
curr = [0 for x in range(n + 1)]
for j in range(1, n + 1):
curr[j] = max(prev[j], curr[j - 1])
if a[i - 1] == b[j - 1]:
curr[j] = max(curr[j], prev[j - 1] + 1)
prev = curr
return curr[n]

if __name__ == '__main__':
a = input().strip()
b = input().strip()
c = set(a) & set(b)
a = "".join([x for x in a if x in c])
b = "".join([x for x in b if x in c])
print(llis(a, b))```
```

Jenny's Subtrees

Jenny loves experimenting with trees. Her favorite tree has n nodes connected by n - 1 edges, and each edge is ` unit in length. She wants to cut a subtree (i.e., a connected part of the original tree) of radius r from this tree by performing the following two steps: 1. Choose a node, x , from the tree. 2. Cut a subtree consisting of all nodes which are not further than r units from node x .

Tree Coordinates

We consider metric space to be a pair, , where is a set and such that the following conditions hold: where is the distance between points and . Let's define the product of two metric spaces, , to be such that: , where , . So, it follows logically that is also a metric space. We then define squared metric space, , to be the product of a metric space multiplied with itself: . For

Array Pairs

Consider an array of n integers, A = [ a1, a2, . . . . an] . Find and print the total number of (i , j) pairs such that ai * aj <= max(ai, ai+1, . . . aj) where i < j. Input Format The first line contains an integer, n , denoting the number of elements in the array. The second line consists of n space-separated integers describing the respective values of a1, a2 , . . . an .

Self Balancing Tree

An AVL tree (Georgy Adelson-Velsky and Landis' tree, named after the inventors) is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. We define balance factor for each node as : balanceFactor = height(left subtree) - height(righ

Array and simple queries

Given two numbers N and M. N indicates the number of elements in the array A[](1-indexed) and M indicates number of queries. You need to perform two types of queries on the array A[] . You are given queries. Queries can be of two types, type 1 and type 2. Type 1 queries are represented as 1 i j : Modify the given array by removing elements from i to j and adding them to the front. Ty