Why it works
- If the last letters of two prefixes are equal, some longest common subsequence ends with that letter: whatever the answer used instead can be swapped for it. So the cell is the diagonal plus one.
- If they differ, at least one of the two letters is not at the end of the answer, so the answer is in the cell above or the one to the left: the larger of the two.
- Every cell reads only cells with shorter prefixes, which row-by-row order has already filled. A shared letter in the wrong place, like p here, never adds to the count.
Complexity
Time O(n × m) for words of lengths n and m: one cell per pair of prefixes, each filled from three neighbours. Memory O(n × m) for the table; keeping only the row above brings it down to O(m).
nextNow solve it yourself, no hints.
Solve on LeetCode ↗