# Common Child challenge

**Problem statement**

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

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

For example, `ABCD`

and `ABDC`

has two children with maximum length , `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, and , 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 and respectively. `lcs[i][j]`

will hold the length of the for `a[:i]`

and `b[:j]`

.

The algorithm looks as follows:

1. Iterate over the strings and .

2. Let and be the current indices for and respectively.

3. Compare `a[i]`

and `b[j]`

:

1. If the characters at index and match then the length of the is equal to:

2. If the characters at index and do not match then the length of the is equal to:

**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:

Space complexity:

#### 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 matrix to store our previous calculations for the previous subproblems. Since we know that both strings have the same length, , it suffices to use a matrix of size .

**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