Recently i did Leetcode Longest Common Subsequence problem. I used the basic dp approach and solved it in 18 ms using 12 mb space. After that i decided to check the fastest solutions for the problem and got this code
Fastest LCS code
I submitted it and it ran in 4 ms using 7.5 mb space. I tried to deconstruct the algorithm and understand how it was working. I cleaned the code a bit and got it to run in 3 ms, but I still could not understand it.
My optimized code
I could not find any relevant blogs explaining it. Can anyone help me understand how this works or link any blogs. Thanks.
Auto comment: topic has been updated by ClosetNarcissist (previous revision, new revision, compare).
I have simplified the code as much as i can and this is what i got
It is slower now, getting AC at 106ms, using 9.4mb (way worse than even the basic solution to LCS) but it does a fine job of representing what the code in question is actually doing.
Deconstructing the code did give me a greater insight into it but I still don't have a complete idea of how it works.
One thing to note is that the last loop where the bitset L is getting modified, contains the Longest Common Subsequence between string Y and the substring of X from [0, i] after each iteration. So, you could make an vector array of size n and store the L.count() after every iteration to return it and use it in main.
P.S. If you have a better implementation of bigint then you can easily make this algorithm faster. My bitset implementation of bigint, while providing me with clarity, was obviously more slower than the bigint implementation in the original code (Thus resulting in more time taken).
ClosetNarcissist see here: A Bit-String Longest-Common-Subsequence Algorithm