- Practice
- Algorithms
- Strings
- Common Child
- Discussions

# Common Child

# Common Child

Spatzist + 10 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 + 0 comments 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]

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 + 2 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 + 0 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

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 + 1 comment 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.

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 + 0 comments 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!

rwan7727 + 5 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 + 0 comments bottom up works perfectly but TLE in top down memoization approaches

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

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 + 2 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

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.

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.

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.

cool_shark + 1 comment 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]

shvburade + 0 comments I tried still 6 timeouts, python 3

Sort 279 Discussions, By:

Please Login in order to post a comment