- Practice
- Algorithms
- Strings
- Common Child
- Discussions

# Common Child

# Common Child

Spatzist + 12 comments Relevant Wikipedia article: https://en.wikipedia.org/wiki/Longest_common_subsequence_problem

A straightforward solution uses O(n^2) time and space. Optimizations can reduce both of these.

neverloseks + 0 comments so much thanks for your link... i'm in hell before reading the wiki... i have to learn more on dynammic programming....

saru_sweety99 + 0 comments Thank you sooo much for this link.It helped me a lot.

markestudillo + 0 comments Thank you for the link! Really helped understand the concept of obtaining the LCS.

it_henrik + 1 comment thanks for the link, I had stubbornly been banging my head on this one for quite a while (some days) before checking in here :)

So if someone else is struggling with their python3 solution here is mine with explanations on what is happening and why.

To see the sequence of letters just uncomment the lines working on the lcs_letters matrix, it wont pass all tests though

def commonChild(s1, s2): # row 0 = 0, column 0 = 0 l1 = len(s1) l2 = len(s2) # we only need history of previous row lcs = [[0]*(len(s1)+1) for _ in range(2)] #lcs_letters = [['']*(len(s1)+1) for _ in range(2)] # i in s1 = i+1 in lcs for i in range(l1): # get index pointers for current and previous row li1 = (i+1)%2 li = i%2 # j in s1 = j+1 in lcs for j in range(l2): # i and j are used to step forward in each string. # Now check if s1[i] and s2[j] are equal if s1[i] == s2[j]: # Now we have found one longer sequence # than what we had previously found. # so add 1 to the length of previous longest # sequence which we could have found at # earliest previous position of each string, # therefore subtract -1 from both i and j lcs[li1][j+1] = (lcs[li][j] + 1) #lcs_letters[li1][j+1] = lcs_letters[li][j]+s1[li] # if not matching pair, then # get the biggest previous value elif lcs[li1][j] > lcs[li][j+1]: lcs[li1][j+1] = lcs[li1][j] #lcs_letters[li1][j+1] = lcs_letters[li1][j] else: lcs[li1][j+1] = lcs[li][j+1] #lcs_letters[li1][j+1] = lcs_letters[li][j+1] #print(lcs_letters[(i+1)%2][j+1]) return lcs[(i+1)%2][j+1]

josef_klotzner + 1 comment it is (too slow) working thanks to the fact, if strings s1 and s2 have equal length. If not -> key error your bug: you need to build your lcs table based on len (s2) (which is l2) hint beside: you have defined l1 and l2, but every time you could use it you write len (s1) instead of just l1 - same for l2, s2 your lcs_letters part, which is marked as comment is terribly wrong. instead of just collecting strings in your lcs_letters you need to collect list of strings (there are more results with same length). if you found matching character you need to add it to each collected string. xou need to separate left > above, left < above and left == above if left == above you need to merge collected string lists (f.e. list(set(left + above) i changed all that and more and now it not only passes this challenge, it is useful, because not only returning a number of result, also the specific results in detail .... maybe later on this might be useful to have he he :=)

Here we go: my python3 solution also with complete list of solutions with same length for lcs_letters (i might be the only one solving it with python3), which you can see, if you solved the challenge. If you did not solve only because of timeout put your code to a pypy3 window and zoooooom, solved :) https://www.hackerrank.com/challenges/common-child/submissions/code/115183048

Sravan_Turibilli + 1 comment Why does it work in pypy3 and not in python 3 ?

Can anyone clarify this, Thanks in advance

samjlb11 + 0 comments PyPy executes faster in some cases. I believe the following article would help. https://www.infoworld.com/article/3385127/what-is-pypy-faster-python-without-pain.html

WittyNotes + 1 comment Thank you so much. Been beating my brains over this, and it's nice to know that it's a common problem in Computer Science.

puneetkaur + 3 comments Idk what is messed up with this :

#!/bin/python3 def lcs(str1, str2): arr = [[0]* len(str1)]*len(str2) for i in range(len(str2)): for j in range(len(str1)): if i==0 or j==0: if str2[i]==str1[j]: arr[i][j]=1 else: arr[i][j]=0 else : if str2[i]==str1[j] : arr[i][j] = arr[i-1][j-1]+1 else : arr[i][j] = max(arr[i-1][j], arr[i][j-1]) # print(arr[i]) return arr[-1][-1] str1 = input().strip() str2 = input().strip() print(lcs(str1, str2))

mywork_koder + 0 comments You have problem with filling the first row and first line For example You have 2 strings AXX AYY

Expected long_common_sequence_table for first row and line is:

1 1 1 1 1

Acual long_common_sequence_table for first row and line is: 1 0 0 0 0

umyarovrr + 3 comments @puneetkaur, are you sure you want to define your

`arr`

this way?`arr = [[0]* len(str1)]*len(str2)`

will actually give you a list with n same lists. Take a look:arr = [[0] * 2]*2

print(arr)

[[0, 0], [0, 0]]

arr[1][1] = 1

print(arr)

[[0, 1], [0, 1]]

Sorry, if its irrelevant. Just I am new to python and faced this problem myself

josef_klotzner + 0 comments this is relevant. you are absolutely right. i am defining therefore this way f.e.:

cs1 = [[0] for _ in range (26)]

ismailkuet + 0 comments [deleted]ismailkuet + 0 comments @umyarovrr ... Defination should be like ::

arr = [[0 for x in range(2)] for y in range(2)]

AmoghBharti + 0 comments # First change your arr declartion arr = [[0 for _ in range (len(str1))] for _ in range(len(str2))] # and change this inside the loop if i==0: if str2[i]==str1[j]: arr[i][j]=1 else: arr[i][j]=a[i][j-1] else if j==0: if str2[i]==str1[j]: arr[i][j]=1 else: arr[i][j]=a[i-1][j]

Sirius19 + 0 comments Thank you, you save me

malika_messaoud1 + 0 comments Thank you so much Spatzist this link is really helpful even if i didn't understand the whole article but i understant the essatial, because there a lot of details.

prabhjeet6 + 0 comments thanks man, i have forgotten all that too quickly

ejubkadric + 2 comments In case you want to get to the point and avoid unnecessary info on wikipedia, check out this video: https://www.youtube.com/watch?v=NnD96abizww It explains how to solve the longest common subsequence problem. Using that I was able to implement a solution to this problem. Cheers :)

1634810123_coe3b + 0 comments Did all test cases pass? I am getting timeout in 4 in python.

amitk_81 + 1 comment Awasome, could able to do it with charm after watching this. C# code:

static int commonChild(string s1, string s2) { int[,] mat = new int[s1.Length+1, s2.Length+1]; for(int i=0; i<= s1.Length; i++){ mat[i,0] = 0; mat[0,i] = 0; }

`for(int i = 0; i < s1.Length; i++){ for(int j = 0; j < s2.Length; j++){ if(s1[i] == s2[j]){ mat[i+1,j+1] = mat[i, j] + 1; } else{ mat[i+1,j+1] = mat[i+1, j] > mat[i, j+1] ? mat[i+1, j] : mat[i, j+1]; } } } return mat[s1.Length, s1.Length]; }`

gabrielbb0306 + 0 comments Nice! Only one suggestion: Consider using Math.max() function in your else statement.

AmoghBharti + 1 comment I used C++ and that failed a few test cases. I tried looking for solution, and just because someone declared the Matrix as "static" the solution accepted.

pk35008 + 2 comments May i know what exactly is to be done here. I've brainstorming for quite a while now. My code:

int commonChild(string s1, string s2) {

int LCS[s1.size()+1][s2.size()+1];

for(int i=0;i<=s1.size();i++) { for(int j=0;j<=s2.size();j++) { if(i==0||j==0) LCS[i][j]=0;

`else if(s1[i-1]==s2[j-1]) LCS[i][j] = 1+ LCS[i-1][j-1]; else LCS[i][j] = max(LCS[i-1][j],LCS[i][j-1]); }`

}

return LCS[s1.size()][s2.size()];

}

AmoghBharti + 2 comments static int LCS[5001][5001]; //change required bcz it saves memory otherwise some test cases may fail bcz of segmentation fault

pk35008 + 0 comments why static? I mean, test cases are failing if i did not include static. What is the reason

trungvthe130284 + 0 comments Thanks this helped me also.

AmoghBharti + 2 comments but there is a more optimised solution to this, in which we don't have to create a full matrix, just two rows will work.

pk35008 + 0 comments would be delighted if more insights are added to this, thank you

josef_klotzner + 1 comment one row to store "history of a line " is enough, which is swapped with current row on end

pk35008 + 0 comments brilliant!

160103022ECEA + 0 comments Thank You

rdn32 + 10 comments Using Python, I was having some trouble getting test case #5 running sufficiently quickly to pass. One of my problems was to do with unnecessarily making the memory use quadratic in the problem size, but that's kind of an algorithm problem. The other is specific to Python, and is a bit subtle so I thought it would be worth describing: 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. Once you've got the algorithm right, this second issue makes a surprising amount of difference to performance.

scotthellam + 0 comments Thanks! That made enough of a difference to pass test #5.

ygh929 + 1 comment Thanks! your comment helps a lot to pass test #5!

prashant_93_y + 2 comments @rdn32, @scotthellam, @ygh929 can you guys please tell me how to optimize my code to pass 5th test case http://ideone.com/PmRSaA

opanon + 1 comment That looks fine to me. Are you still having issues?

cyestoner + 1 comment I ran into this problem with python3. Using python2 "Worked For Me".

Some digging on the issue makes me think that there are some performance problems with list indexing on python3 that might cause enough of a slowdown to fail the 10s timer.

SidSam + 2 comments I'm using Python2 too, but using that code, 5 test cases terminate due to timeout. Test cases 9 to 13.

arpitvarshney + 1 comment Apply DP. Its not required to generate the full matrice as we need only two rows at a time. That may give a hint.

jake_griffin + 1 comment Yes, and you don't even need two rows. I used one row, and saved the last overwritten value in another variable. The part of the row "to the left" of current processing posision was like your "row 2", and the part of the row "to the right" was like your "row 1". The extra variable was to store the number that was last overwritten from row 1.

cakaroo + 0 comments Using 2 raw it works in Python 2 but not in python 3.

Varun_Rathi0623 + 0 comments yes for me too how did you solved them

subashm6 + 0 comments [deleted]

gregory_geller + 2 comments I would have never figured out why I was timing out in case #5 without this hint. Where can I find out more about the relative performance of file scope vs function scope in python?

TonyKim + 0 comments I wouldn't have figure out why I was timing out without this hint too. I would be also interested with any references about file scope vs function scope

TonyKim + 0 comments I found some details about the reason why function scope is faster! http://http://stackoverflow.com/questions/11241523/why-does-python-code-run-faster-in-a-function

akshayc11 + 1 comment I am unsure what you mean by this. I am not an expert python programmer. Could you suggest further sources / examples where I can read up on what you mean? I created a function as described, with the non-recursive version of the algorithm. However, I am still facing the timeout issue in case 5. I am also using O(2m) additional memory.

Are there any other optimizations that I am missing?

aneeshkher + 1 comment What is the time complexity of your solution? It should not exceed O(mn).

akshayc11 + 0 comments It does not. It is O(mn)

shravanc6 + 0 comments I was surprised that moving my code into a function solved TLE for last 5 test cases. Had a hard time figuring this out, but I see that rdn32 has already mentioned it. Something I learned today.

emir13 + 0 comments Wow! Interesting, thanks!

emir13 + 1 comment Its really interesting! while same code only passes half of the test cases with Python3, with Python2 it passes all test cases. Why it differs that much? Any answer is appreciated!

josef_klotzner + 1 comment Good question. usually python3 is much faster than python2. i compared them in lots of exercises here. in this specific case python2 is really approximatly 20 % faster than 3. i solved this by using pypy3. (own test data 5000 characters for s1 and s2

pypy3: 0,7 s

python 3: 8,8 s

python 2 7 s

josef_klotzner + 0 comments the difference between python2 and python3 in this case is only 20%. i did perfomance tweaks

(only using one dimension row for history, build up new and then swap, i observed that max function is slower than compare by my own)

and doubled the speed this way. Now the difference is irrelevant. i think i might be the only one who solved it with python3 my testcase on my machine:

pypy 3: 0,4 s

python3: 4,7 s

python2: 4,2 s

https://www.hackerrank.com/challenges/common-child/submissions/code/115183048

rwan7727 + 7 comments In c++:

`string s1; cin >> s1; string s2; cin >> s2; // matrix c stores the char count of child string vector < vector<int> > c(s1.length()+1,vector<int>(s2.length()+1)); for (int i=1;i<=s1.length();i++) { for (int j=1;j<=s2.length();j++) { if (s1[i-1]==s2[j-1]) c[i][j]=c[i-1][j-1]+1; else c[i][j]=max(c[i][j-1], c[i-1][j]); } } cout << c[s1.length()][s2.length()];`

vickaboy + 1 comment bottom up works perfectly but TLE in top down memoization approaches

sravan2366 + 0 comments I also tried top down approach failing

hacker_khan + 1 comment why using dynammic array in c++ solves the issue of timeout??

alimobasshir21 + 1 comment same doubt, segmentation faults if array is used in place of vectors.

Khalil_ammar + 1 comment vectors are stored in the heap while statically declared arrays are stored in the stack. Since the programs are uploaded and tested, the stack allocated for your program is not enough to store a 5000x5000 array.

boiko_ivan + 0 comments You don't need to store 5000 x 5000 array.

You only need to keep 2 rows, last and previous.

shallymittal08 + 0 comments Thanks, replacing array with vector helped a lot.

woldegebrielkeb1 + 1 comment [deleted]woldegebrielkeb1 + 0 comments [deleted]

sharmajikalaunda + 0 comments Thank you so sooo much!!!!

amoghjahagirdar1 + 0 comments One major issue I faced was that I used int array instead of vector. I was repeatedly failing 3-4 cases, I switched to vector and the problem was solved... I dont even know....

amoghjahagirdar1 + 0 comments one question, i have for you is why do we not require to assign the first row and column to be 0, when arrays are used garbage value is returned if we dont do so

shishirsharma + 0 comments Also keep poping old rows from memo which are not needed any more.

19998sachinyadav + 0 comments python2 works fine but python3 gives TLE.......!

Tsukuyomi1 + 4 comments If you get timeout in Python just submit the same solution in PyPy. My code timed out for 6 testcases in Python 3 but got accepted with max time 0.51s in PyPy3

so_no + 0 comments Indeed. That's pretty weird.

songzy12 + 0 comments Thanks!

max_waser + 0 comments Bless you!

boiko_ivan + 0 comments Indeed so.

Kept banging my head against the keyboard for a couple of days...

Even invented algorithm faster than N^2 using binary trees, which was much faster on smaller strings, but was 4 times slower on 5000 length.Then gave up and looked at Discussion :)

nonomus + 6 comments Anyone who is getting the segfault error on test case #5: You are likely programming in C/C++ and are running out of stack space for your array. Use dynamic memory to fix it.

FilipeGoncalves + 1 comment No need to use dynamic memory. Max string size is 5000. Just use a big statically allocated array.

shanur_cse_nitap + 1 comment FilipeGoncalves i solved it using dynamic programming and it passed all test cases .

but i would be glad to know your approach

super4166 + 1 comment i am trying to solve it using longest common subsequence but segmention fault is coming in few cases

utkarshpp + 0 comments U can solve this program by using array of size 2 by min(s1.size(),s2.size())

it won't give segmentation fault Most probably its SIGSEGV, Segmentation fault bcoz of invalid memory pointer reference

ashwinmanoj95 + 1 comment I tried allocating dynamic memory and also increasing the stack space using pragma directive and still my program shows segmentation fault for the fifth test case. can anyone pls help me..thank you

abhishek22 + 4 comments Instead of defining 2d matrix inside a function, define it globally. In this way it will acquire data segment instead of stack memory.

shivalikranaut + 0 comments you just solved my so many problems. Thank you

maverick55 + 0 comments Thanks man. You saved my day.

ppg_0007 + 1 comment oh thanks it helped me..

luckykohli + 0 comments Thanks a lot man

the_piranha + 0 comments Thanks a tonne , you saved my day.

ashishkaila + 0 comments Dynamic memory is not the correct way to handle this. The correct way is to use an iterative solution rather than the recursive solution.

ayushmw1 + 2 comments Need to make dp array global. I don't understand how that solves the problem but it does.

gratitude + 1 comment when u use declare globally it will use stack memory but when u declare it locally it cannot use stack memory and it will only use heap memory which is not enough for the 5th test case..so segfault is expected :)

sheep0x + 0 comments C/C++ local vars, unless declared “

`static`

”, (typically) use stack memory or register or simply disappear at compile time.Dynamic allocation (typically) uses heap area.

Global vars and static local vars and static member vars (typically) use a separate “static” memory area. (If you initialize them to zero and never use them, chances are OS doesn't even allocate memory for them.)

(Terminology differs from tutorial to tutorial but the idea is that there is a separate, pre-allocated part of virtual memory that is neither stack nor heap.)

See w:Data segment and cppreference:storage duration for more details. If you have a Linux box, you can also try toying with stack limit using

`ulimit`

(assuming you are using Bash/Zsh).

MystikNinja + 0 comments The same change solved it for me as well.

RryLee + 0 comments like this

int **array = new int*[length + 1]; for (int i = 0; i < length + 1; ++i) { array[i] = new int[length + 1]; }

manish_pal + 0 comments Dynamic allocation of 2D array helped me pass all the test cases. Thanks.

v_balazs + 3 comments My solution is based on the following article from wikipedia: https://en.wikipedia.org/wiki/Longest_common_subsequence_problem

public class Solution { static int commonChild(String a, String b){ int[][] C = new int[a.length()+1][b.length()+1]; for (int i = 0; i < a.length(); i++) { for (int j = 0; j < b.length(); j++) { if (a.charAt(i) == b.charAt(j)) { C[i+1][j+1] = C[i][j] + 1; } else { C[i+1][j+1] = Math.max(C[i+1][j], C[i][j+1]); } } } for (int i = 0; i < a.length(); i++) { } return C[a.length()][b.length()]; } public static void main(String[] args) { Scanner in = new Scanner(System.in); String s1 = in.next(); String s2 = in.next(); int result = commonChild(s1, s2); System.out.println(result); } }

houqisen + 0 comments Thanks for sharing. I am studying on this solution.

h674734481 + 0 comments Nice try，Thx

Abe10 + 0 comments There is an extra for loop just before the return statement. I dont think it does anything. Remove it if anyone is copying this code. Cheers!

sigbusyff + 2 comments I'm a little bit surprised there's only 30 points up for grabs for this one. It's got a very low success rate, and would arguably be more at home in the "Dynamic Programming" area...

whoan + 0 comments Agree with you @sigbusyff. On the other hand, the "Resources" section give good hints about how to solve the problems. In this particular exercise, "Dynamic Programming Basics" is in the list BTW.

dsun092 + 2 comments For anyone having trouble passing TLE using DP in python2, if you are using the max function, try swapping that out for if else statement... thanks cucux for pointing it out!

Samuel_Russell + 0 comments This was helpful to me. No idea why max is so much slower than else if.

Liviul + 0 comments Same problem in Python3: eliminate it and it goes fast enough.

cool_shark + 2 comments Variation of LCS by using two alternating rows instead of a full list and by replacing

`max`

with`if else`

to avoid time-out errors.def commonChild(s1, s2): m, n = len(s1), len(s2) prev, cur = [0]*(n+1), [0]*(n+1) for i in range(1, m+1): for j in range(1, n+1): if s1[i-1] == s2[j-1]: cur[j] = 1 + prev[j-1] else: if cur[j-1] > prev[j]: cur[j] = cur[j-1] else: cur[j] = prev[j] cur, prev = prev, cur return prev[n]

olegcherednik + 1 comment static int commonChild(String s1, String s2) { int[][] arr = new int[s1.length() + 1][s2.length() + 1]; for (int i = 0; i < s1.length(); i++) for (int j = 0; j < s2.length(); j++) arr[i + 1][j + 1] = s1.charAt(i) == s2.charAt(j) ? arr[i][j] + 1 : Math.max(arr[i][j + 1], arr[i + 1][j]); return arr[s2.length()][s1.length()]; }

meet_lovelyac + 2 comments Hi. why are you keeping the size of arr as s1.length()+1 and s2.length()+1?

sardanagautam121 + 0 comments watch this, you will understand : https://www.youtube.com/watch?v=sSno9rV8Rhg

sumanconstantin + 0 comments Because you need to work with previous values.

That's why the first values are all '0' on both the line and column, and the value sums start from indeces 1 and 1.

arr[i + 1][j + 1]

That's why you need to allocate an extra cell for both line and column.

Sort 331 Discussions, By:

Please Login in order to post a comment