Spatzist 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 so much thanks for your link... i'm in hell before reading the wiki... i have to learn more on dynammic programming....
saru_sweety99 Thank you sooo much for this link.It helped me a lot.
markestudillo Thank you for the link! Really helped understand the concept of obtaining the LCS.
it_henrik 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 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 Why does it work in pypy3 and not in python 3 ?
Can anyone clarify this, Thanks in advance
samjlb11 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 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 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 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 @puneetkaur, are you sure you want to define your
arrthis 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 this is relevant. you are absolutely right. i am defining therefore this way f.e.:
cs1 = [[0] for _ in range (26)]
ismailkuet [deleted]ismailkuet @umyarovrr ... Defination should be like ::
arr = [[0 for x in range(2)] for y in range(2)]
AmoghBharti # 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 Thank you, you save me
malika_messaoud1 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 thanks man, i have forgotten all that too quickly
ejubkadric 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 Did all test cases pass? I am getting timeout in 4 in python.
amitk_81 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 Nice! Only one suggestion: Consider using Math.max() function in your else statement.
AmoghBharti 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 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 static int LCS[5001][5001]; //change required bcz it saves memory otherwise some test cases may fail bcz of segmentation fault
pk35008 why static? I mean, test cases are failing if i did not include static. What is the reason
trungvthe130284 Thanks this helped me also.
AmoghBharti 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 would be delighted if more insights are added to this, thank you
josef_klotzner one row to store "history of a line " is enough, which is swapped with current row on end
pk35008 brilliant!
160103022ECEA Thank You
rdn32 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 Thanks! That made enough of a difference to pass test #5.
ygh929 Thanks! your comment helps a lot to pass test #5!
prashant_93_y @rdn32, @scotthellam, @ygh929 can you guys please tell me how to optimize my code to pass 5th test case http://ideone.com/PmRSaA
opanon That looks fine to me. Are you still having issues?
cyestoner 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 I'm using Python2 too, but using that code, 5 test cases terminate due to timeout. Test cases 9 to 13.
arpitvarshney 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 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 Using 2 raw it works in Python 2 but not in python 3.
Varun_Rathi0623 yes for me too how did you solved them
subashm6 [deleted]
gregory_geller 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 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 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 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 What is the time complexity of your solution? It should not exceed O(mn).
akshayc11 It does not. It is O(mn)
shravanc6 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 Wow! Interesting, thanks!
emir13 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 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 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 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 bottom up works perfectly but TLE in top down memoization approaches
sravan2366 I also tried top down approach failing
hacker_khan why using dynammic array in c++ solves the issue of timeout??
alimobasshir21 same doubt, segmentation faults if array is used in place of vectors.
Khalil_ammar 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 You don't need to store 5000 x 5000 array.
You only need to keep 2 rows, last and previous.
shallymittal08 Thanks, replacing array with vector helped a lot.
woldegebrielkeb1 [deleted]woldegebrielkeb1 [deleted]
sharmajikalaunda Thank you so sooo much!!!!
amoghjahagirdar1 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 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 Also keep poping old rows from memo which are not needed any more.
19998sachinyadav python2 works fine but python3 gives TLE.......!
Tsukuyomi1 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 Indeed. That's pretty weird.
songzy12 Thanks!
max_waser Bless you!
boiko_ivan 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 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 No need to use dynamic memory. Max string size is 5000. Just use a big statically allocated array.
shanur_cse_nitap FilipeGoncalves i solved it using dynamic programming and it passed all test cases .
but i would be glad to know your approach
super4166 i am trying to solve it using longest common subsequence but segmention fault is coming in few cases
utkarshpp 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 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 Instead of defining 2d matrix inside a function, define it globally. In this way it will acquire data segment instead of stack memory.
shivalikranaut you just solved my so many problems. Thank you
maverick55 Thanks man. You saved my day.
ppg_0007 oh thanks it helped me..
luckykohli Thanks a lot man
the_piranha Thanks a tonne , you saved my day.
ashishkaila 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 Need to make dp array global. I don't understand how that solves the problem but it does.
gratitude 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 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 The same change solved it for me as well.
RryLee like this
int **array = new int*[length + 1]; for (int i = 0; i < length + 1; ++i) { array[i] = new int[length + 1]; }
manish_pal Dynamic allocation of 2D array helped me pass all the test cases. Thanks.
v_balazs 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 Thanks for sharing. I am studying on this solution.
h674734481 Nice try，Thx
Abe10 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 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 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 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 This was helpful to me. No idea why max is so much slower than else if.
Liviul Same problem in Python3: eliminate it and it goes fast enough.
cool_shark Variation of LCS by using two alternating rows instead of a full list and by replacing
maxwithif elseto 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 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 Hi. why are you keeping the size of arr as s1.length()+1 and s2.length()+1?
sardanagautam121 watch this, you will understand : https://www.youtube.com/watch?v=sSno9rV8Rhg
sumanconstantin 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