Commonest Subsequence A string has $2^n$ subsequences, but they are usually not all distinct. What is the complexity of finding the maximum frequency of any subsequence?

For example, the string "subsequence" contains 7 copies of the subsequence "sue" and this is the maximum.

Sample brute-force code at http://ideone.com/UIp3t

Are there related structural theorems? Both of these turn out to be false:


the longest of the maximum-frequency subsequences is unique
the maximum frequency of any length-$k$ subsequence is unimodal in $k$


Possibly related links:


Counting # distinct subsequences $\in \mathbf{P}$ http://11011110.livejournal.com/254164.html
Related contest problem for multiple sources http://www.spoj.pl/problems/CSUBSEQS/
Related paper http://dx.doi.org/10.1016/j.tcs.2008.08.035


Edit 10 days later: thanks for taking a look! I had wondered if this would make a nice polynomial-time solvable programming contest problem. I guess not, but I hope to think about it again later.
from a search, here is a paper with some research &amp; findings for graduate level research but (caveat) no references. it has some heuristics, estimates, empirical results &amp; commentary on the problem and some ideas on proving its (approximation) complexity etc.

Identification of Most Frequent Subsequences
CSE 549 Computational Biology Project Final Report
Mikhail Bautin 2006

(while there are some standard subsequence problems that are somewhat similar &amp; studied eg in the Elzinga et al paper, is it possible this particular subsequence problem has not been studied too much?)