Hacker Rank ‘Common Child’ Solution

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.

Link

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:
#!/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()

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

Facebooktwittergoogle_plusredditpinterestlinkedin
  • Sidharth Samant

    Hi Martin. I tried to use this code for the Common Child solution on HackerRank, but 5 test cases terminated due to timeout.

    • Unfortunately these things happen. I guess that HackerRank changed their memory/time constrains for the challenge. I’ve checked some of the old Python submissions by other authors and they use the same approach. It might just be that Python is too slow for their benchmark. Or my implementation of the LCS has a bug in it. Try using the same algorithm in another language 🙂