Given a stack, if we perform intermixed push/pop operations, we could get scrambled string.
For example, given "great", if we perform: push, push, pop, pop, push, push, push, pop, pop, pop
we can get pop sequence like "rgtae", so "rgtae" is a valid scrambled string. And there is no such sequence for "etgar" so "etgar" is not a scrambled string of "great".
To determine if a sequence is valid only takes O(N^2) (as far as I know) but it cannot handle duplicates. So can anyone give a solution of O(N^2), or at least better than O(N^4)?
Scrambled strings not always can be generated by intermixed push/pop operations. For example the string "abcdefgh" has a scrambled string "abefcdgh", and the nearest string generated by push/pop operations is "abefdcgh".
By the way, to determine whether a sequence, with no duplicates, can be generated by applying intermixed push/pop operations only takes O(N), using greedy strategy.