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.