Hackerrank - Common Child Solution
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, and .
Constraints
- All characters are upper case in the range ascii[A-Z].
Output Format
Print the length of the longest string , such that is a child of both and .
Sample Input
HARRY
SALLY
Sample Output
2
Explanation
The longest string that can be formed by deleting zero or more characters from and is , whose length is 2.
Sample Input 1
AA
BB
Sample Output 1
0
Explanation 1
and 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 and while maintaining the order is .
Sample Input 3
ABCDEF
FBDAMN
Sample Output 3
2
Explanation 3
is the longest child of the given strings.
Solution in Pypy3
def commonChild(s1, s2):
m = [[0]*(len(s2)+1) for _ in range(len(s1)+1)]
for i,c in enumerate(s1,1):
for j,d in enumerate(s2,1):
if c == d:
m[i][j] = m[i-1][j-1]+1
else:
m[i][j] = max(m[i][j-1],m[i-1][j])
return m[-1][-1]
print(commonChild(input(), input()))
Note: Time out error with python3. Only works with Pypy3