# HackerRank ‘Common Child’ Solution

H
##### Short Problem Definition:

Given two strings a and b of equal length, what’s the longest string (S) that can be constructed such that it is a child of both?

A string x is said to be a child of a string y if x can be formed by deleting 0 or more characters from y.

Common Child

##### Complexity:

time complexity is O(N*M)

space complexity is O(N*M)

##### Execution:

This is a longest common subsequence problem in disguise. I encourage you to look at a good explanation here.

##### Solution:
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #!/usr/bin/py   def lcs(a, b): lengths = [[0 for j in range(len(b)+1)] for i in range(len(a)+1)] for i, x in enumerate(a): for j, y in enumerate(b): if x == y: lengths[i+1][j+1] = lengths[i][j] + 1 else: lengths[i+1][j+1] = max(lengths[i+1][j], lengths[i][j+1])   return lengths[-1][-1]   def main(): s1 = raw_input() s2 = raw_input() print lcs(s1,s2)   if __name__ == '__main__': main()