<p>Assuming <a href="https://en.wikipedia.org/wiki/Exponential_time_hypothesis" rel="nofollow noreferrer">Exponential Time Hypothesis</a> (which is stricter than P is not equal to NP, but is still widely believed to be true), it is not possible to do it in time O(N^{2 - eps}) for any positive constant eps, see <a href="http://dl.acm.org/citation.cfm?id=2880032" rel="nofollow noreferrer">"Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping"</a> by Karl Bringmann and Marvin Kunnemann (pre-print on arXiv is available).</p>

<p>Roughly speaking, it means that the general case of this problem cannot be solved in time better than something like O(N^2/log N), so if you want faster algorithms you have to consider additional constraints (some properties of the strings) or look for approximate solution.</p>
Finding longest common subsequence in O(NlogN) time
<p>Is there any way of finding the longest common subsequence of two sequences in O(NlogN) time? </p>

<p>I read somewhere that there is a way to achieve this using binary search. </p>

<p>I know the dp approach that takes O(N<sup>2</sup>) time. </p>