## fizzbuzzer

### 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")

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")