Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

Common Child challenge

Sharing is caring!

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

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

For example, ABCD and ABDC has two children with maximum length \textit{3}, ABC and ABD. Note that we will not consider ABCD as a common child because C doesn’t occur before D in the second string.

Input format
Two strings, \textit{a} and \textit{b}, with a newline separating them.

Constraints
All characters are upper cased and lie between ASCII values 65-90. The maximum length of the strings is 5000.

Output format
Length of string S.

Sample Input 0

HARRY
SALLY

Sample Output 0

2

The longest possible subset of characters that is possible 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

AA and BB has no characters in common and hence the output is 0.

Sample Input 2

SHINCHAN
NOHARAAA

Sample Output 2

3

The largest set of characters, in order, between SHINCHAN and NOHARAAA is NHA.

Sample Input 3

ABCDEF
FBDAMN

Sample Output 3

2

BD is the longest child of these strings.

Solution using Dynamic Programming

We define a 2-dimensional matrix lcs = int[n][m], where n and m is the length of the strings \textit{a} and \textit{b} respectively. lcs[i][j] will hold the length of the \textit{Longest Common Subsequence (lcs)} for a[:i] and b[:j].

The algorithm looks as follows:
1. Iterate over the strings \textit{a} and \textit{b}.
2. Let \textit{i}<=n and \textit{j}<=m be the current indices for \textit{a} and \textit{b} respectively.
3. Compare a[i] and b[j]:
1. If the characters at index \textit{i} and \textit{j} match then the length of the \textit{lcs} is equal to: 1 + lcs[i-1][j-1]
2. If the characters at index \textit{i} and \textit{j} do not match then the length of the \textit{lcs} is equal to: max(lcs[i-1][j],lcs[i][j-1])

Solution

import sys

f = open("in.txt")

a, b = f.readline().strip(), f.readline().strip()

n = len(a) + 1
m = len(b) + 1

lcs = [[0]*(n) for i in range(m)] # lcs[i][j] holds the length of the LCS between a[:i] and b[:j] 

maximumLength = 0
for i in range(1, n):
    for j in range(1, m):
        if (a[i-1] == b[j-1]):
            lcs[i][j] = lcs[i-1][j-1] + 1
        else:
            lcs[i][j] = max(lcs[i][j-1],lcs[i-1][j])
            
        maximumLength = max(maximumLength, lcs[i][j])

                
print (maximumLength)   

Complexity:
Time complexity: \mathcal{O}(nm)
Space complexity: \mathcal{O}(nm)

Optimizing the DP Solution

Optimization 1
Although the program can be written without defining a function to do the work (as it only needs to solve one case), accessing file scope variables is slower than function scope variables. – Thanks go out to rdn32 from the HackerRank discussion boards.

Optimization 2
We don’t need a \textit{mn} matrix to store our previous calculations for the previous subproblems. Since we know that both strings have the same length, \textit{n}, it suffices to use a matrix of size \textit{2n}.

Optimization 3
We are also using enumerate() instead of range() as it tends to be slightly faster.

Optimization 4
We omited the second max() computation after each outer iteration.

import sys


def solve(a,b):
    n = len(a) + 1
    lcs = [[0]*(n) for i in range(2)]
    index = 0
    for i, x in enumerate(a):
        index = abs(index - 1)
        for j, y in enumerate(b):
            if (x == y):
                lcs[index][j+1] = lcs[index-1][j] + 1
            else:
                lcs[index][j+1] = max(lcs[index][j],lcs[index-1][j+1])
                
    return max(lcs[0][-1],lcs[1][-1])   
    
def main():
    f = open("in.txt")
    a, b = f.readline().strip(), f.readline().strip()  
    print (solve(a,b))

main()

Notebook file
https://github.com/lucaslouca/coding-problems/tree/master/python/CommonChild