A subsequence of a string is what remains after deleting any number of its characters (possibly none), keeping the rest in their original order. For example, bed is a subsequence of bread, but deb is not.
Given two strings text1 and text2, return the length of the longest string that is a subsequence of both. If they share no letter at all, return 0.
one appears in order in both: it is the last three letters of stone, and longest has an o, then an n, then an e. No common subsequence has four letters.
bluet is a common subsequence: blue at the start of both, then the t near the end of each.
Every letter appears in both, but their orders are reversed, so any two letters come in opposite orders. A single letter is the best possible.
Constraints
1 <= text1.length, text2.length <= 1000text1 and text2 are made of lowercase English letters only.Look at the last letter of each string. If they're equal, that letter can end the common subsequence. If not, at least one of the two isn't used, so drop one and try both ways.
Look only at the last letter of each string. There are two cases.
Time O(n · m)Space O(n · m)
The full walkthrough and code are part of Premium
3