O(n) non Dp solution


#1

If a subsequence of length greater than 2 has repeated, then a subsequence of length 2 will definitely repeat.
So this problem just reduces to checking if a subsequence of length 2 (has repeated (which is a much simpler version).
Now check for all possible strings of length 2 ( you will have 26X26=676 of them) whether they have repeated as subseuence of the string. This is an O(n) operation.
So the overall complexity comes out to be 676X O(n) which is essentially O(n).


#2

But your Solution is Not Optimal for all cases , i don’t know how you assumed that only alphabets will be there like this is not mentioned in question there can be any characters out of 256 then your approach will take O(256X256Xn) which is not O(n).Your code might have passed due to cases only including alphabets.