I tried to use LCS but with the given constraints I was sure to get a TLE.