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 .
ABDC has two children with maximum length ,
ABD. Note that we will not consider
ABCD as a common child because
C doesn’t occur before
D in the second string.
Two strings, and , with a newline separating them.
All characters are upper cased and lie between ASCII values 65-90. The maximum length of the strings is 5000.
Length of string S.
Sample Input 0
Sample Output 0
The longest possible subset of characters that is possible by deleting zero or more characters from
AY, whose length is 2.
Sample Input 1
Sample Output 1
BB has no characters in common and hence the output is 0.
Sample Input 2
Sample Output 2
The largest set of characters, in order, between
Sample Input 3
Sample Output 3
BD is the longest child of these strings.
Solution using Dynamic Programming
We define a 2-dimensional matrix
lcs = int[n][m], where
m is the length of the strings and respectively.
lcs[i][j] will hold the length of the for
The algorithm looks as follows:
1. Iterate over the strings and .
2. Let and be the current indices for and respectively.
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:
import sys f = open("in.txt") a, b = f.readline().strip(), f.readline().strip() n = len(a) + 1 m = len(b) + 1 lcs = [*(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)
Optimizing the DP Solution
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.
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 .
We are also using
enumerate() instead of
range() as it tends to be slightly faster.
We omited the second
max() computation after each outer iteration.
import sys def solve(a,b): n = len(a) + 1 lcs = [*(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[-1],lcs[-1]) def main(): f = open("in.txt") a, b = f.readline().strip(), f.readline().strip() print (solve(a,b)) main()