The string “ABC” occurs in “ABBC” twice, if you remove any characters you wish from “ABBC”.
The following algorithm finds such occurences in O(n) time given any two strings.
One assumption worth noting for the O(n) time bound is that the size of the alphabet is limited to some constant size.
Nested loops in this algorithm scream O(n^2)!! [...]

I wrote some python code that extracts the longest non-decreasing subsequence from any given sequence.
This runs in O(n log n) time, and uses O(n) memory.
”’ An item in the final sequence, used to form a linked list. ”’
class SeqItem():
val = 0 # This item’s value.
[...]