<p>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.</p>

<p><a href="http://bautin.org/pdf/most_freq_subseq.pdf" rel="noreferrer">Identification of Most Frequent Subsequences</a><br>
CSE 549 Computational Biology Project Final Report<br>
Mikhail Bautin 2006</p>

<p>(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?) </p>

CC BY-SA 3.0
2012-08-28T17:33:21.030Z
I don't understand why this was downvoted. It may not be a very deep paper but it appears to be directly on topic.
David Eppstein
CC BY-SA 3.0
2012-08-29T15:54:11.900Z
fyi/addendum Bautin also says at the end of paper he has 5K lines of C++ & Python code on the problem/paper for anyone interested
vzn
CC BY-SA 3.0
2012-08-29T16:14:53.070Z
@David, I don't think the downvote is because of the linked paper, it is probably more to do with the fact that this answer looks like (essentially) a one line link answer (without explaining how the paper is related to the question and answers it). This might have been more appropriate as a comment.
Kaveh
CC BY-SA 3.0
2012-08-29T16:33:23.147Z
ok kaveh, then, spelled out: the paper seems to reveal (unless anyone can find a better ref or come up with proof of this difficult problem themself) that _the exact complexity of the problem is so far unknown/open_ (other than the obvious PSpace/ExpTime) and _may contain the best known analysis/approaches to solving it so far_
vzn
CC BY-SA 3.0
2012-08-29T16:41:20.513Z
I did find this paper before and apologize for not linking to it above, which was since I didn't think it gave much concrete information. I sent the author an email some time ago asking if there was any more he could say about anything that happened since it was written, but got no reply yet.
daveagp
CC BY-SA 3.0
2012-08-28T15:50:34.237Z
2012-08-28T15:50:34.237Z
vzn
<p>Not an answer, just a lemma.</p>

<p>So first of all one might wonder what the commonest subsequence of strings like 12..t12..t12..t.. is. After a little thinking one realizes that it must also have the form 12..t12..t12.., just obviously shorter. If the original string has length nt, and the subsequence of this special form has length k, then the number of its occurrences is exactly ${n+k-\lceil k/t\rceil \choose k}={n+k-\lceil k/t\rceil \choose n-\lceil k/t\rceil}$. This implies that the most common subsequence also ends with $t$ (i.e. $k$ has to be divisible by $t$). But where does this take its maximum and how much is it??? Quite embarassing, but I could not figure it out...</p>

CC BY-SA 3.0
2012-08-26T07:40:24.457Z
2012-08-29T07:22:19.197Z
2012-08-29T07:22:19.197Z
domotorp
<p>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?</p>

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

<p>Sample brute-force code at <a href="http://ideone.com/UIp3t">http://ideone.com/UIp3t</a></p>

<p>Are there related structural theorems? Both of these turn out to be <strong>false</strong>:</p>

<ul>
<li>the longest of the maximum-frequency subsequences is unique</li>
<li>the maximum frequency of any length-$k$ subsequence is unimodal in $k$</li>
</ul>

<p>Possibly related links:</p>

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

<p><em>Edit 10 days later:</em> 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.</p>

CC BY-SA 3.0
2012-08-15T00:56:21.307Z
A possibly naive initial question: is it clear that this problem is even in **NP**? That is to say: for the problem of determining whether there is a subsequence with at least *k* occurances in an *n*-character string, what would a certificate look like? For instance, listing all tuples of indices indicating the instances of a given subsequence would fail to be polynomial sized for the string *aaa...aa* (which, while a boring input, nevertheless has a substring with roughly $n \mathbf C (n/2)$ occurances).
Niel de Beaudrap
CC BY-SA 3.0
2012-08-15T02:21:23.260Z
@Niel de Beaudrap: I think that we can count the number of occurrences as subsequences in polynomial time by dynamic programming, making it possible to use the subsequence itself as a certificate.
Tsuyoshi Ito
CC BY-SA 3.0
2012-08-16T22:25:32.483Z
recently studied something vaguely similar. 3 problems that seem related such that a solution might use similar ideas. [longest repeated substring](http://en.wikipedia.org/wiki/Longest_repeated_substring_problem), [Longest common subsequence problem](http://en.wikipedia.org/wiki/Longest_common_subsequence_problem), [longest common substring problem](http://en.wikipedia.org/wiki/Longest_common_substring_problem). useful is the [suffix tree](http://en.wikipedia.org/wiki/Suffix_tree) or [generalized suffix tree](http://en.wikipedia.org/wiki/Generalised_suffix_tree)
vzn
CC BY-SA 3.0
2012-08-17T15:31:19.547Z
re TIs comment, (1) can you sketch that out further? is it in P to count the occurences of a known subsequence? (2) dont see how knowing the total # occurrences of the subsequence proves that its the maximum. (but, probabilisticly, yeah, one could randomly sample other known subsequences and verify that its count is always larger than theirs.)
vzn
CC BY-SA 3.0
2012-08-18T01:31:12.963Z
@vzn: What I meant is that the usual decision version (which Niel stated in his comment) is in NP.  It does not give a certificate for maximality, of course.  I do not think that your procedure is a correct probabilistic verification procedure for maximality in the sense of [MA](http://qwiki.stanford.edu/index.php/Complexity_Zoo:M#ma), if that is what you meant.
Tsuyoshi Ito
CC BY-SA 3.0
2012-08-18T02:10:03.617Z
not claiming my sketch fits into any particular class, its just a probabilistic algorithm given a subroutine that can count the occurrences of a given subsequence. what exactly is the related/similar/"usual" NP version/problem? nobody seems to have pointed to any std NP problem so far...?
vzn
CC BY-SA 3.0
2012-08-18T03:04:31.377Z
@vzn: I already answered your question in my previous reply to you.  Read Niel’s comment more carefully.
Tsuyoshi Ito
CC BY-SA 3.0
2012-08-25T00:13:31.263Z
I'm a little confused: is the question "given a string s, find the subsequence that occurs the maximum number of times?"
Suresh Venkat
CC BY-SA 3.0
2012-08-25T02:39:25.113Z
@SureshVenkat: Yes, that's my understanding.  For example, given a sequence of $n$ X's as input, the correct answer would be a sequence of $n/2$ X's.
Jeffε
CC BY-SA 3.0
2012-08-26T08:14:43.673Z
@daveagp: [this question on stackoverflow seems the same](http://stackoverflow.com/questions/6877249/find-the-number-of-occurrences-of-a-subsequence-in-a-string) (see aioobe's good answer that uses dynamic programming).
Marzio De Biasi
CC BY-SA 3.0
2012-08-26T11:55:05.573Z
@marzio-de-biasi: the question you linked to is different (and much easier): there you are given the subsequence.
david
CC BY-SA 3.0
2012-08-28T15:31:50.883Z
lemma 3 of [this paper, algorithms for subsequence combinatorics by Elzinga et al](http://compalg.inf.elte.hu/~tony/Kutatas/PerfectArrays/Elzinga-AlgorithmsSubsequenceCombinatorics.pdf) looks close to me, it counts the k-long subsequences. maybe it can be modified without too much trouble to count each one of the k-long subsequences.
vzn
CC BY-SA 3.0
2013-03-25T23:33:44.220Z
Is there a $c<1$, such that a shortest commonest subsequence has length at most $cn$? I made the conjecture with $\lceil \frac{n}{2}\rceil$, but here is a counterexample if my code was correct: The length 14 string $ababaaabbbabab$ has a shortest commonest subsequence of length 8, $abaabbab$. If there is such a $c$, then it would give us an algorithm at least a bit better than the naive $O(2^n)$ one.
Chao Xu
<ds.algorithms><string-search>
Commonest Subsequence
daveagp
# Commonest Subsequence

(Asked by: username_0 on 2012-08-14)

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.

**Tags:** ds.algorithms, string-search

> **Comments:**
> **username_1**: A possibly naive initial question: is it clear that this problem is even in **NP**? That is to say: for the problem of determining whether there is a subsequence with at least *k* occurances in an *n*-character string, what would a certificate look like? For instance, listing all tuples of indices indicating the instances of a given subsequence would fail to be polynomial sized for the string *aaa...aa* (which, while a boring input, nevertheless has a substring with roughly $n \mathbf C (n/2)$ occurances).  
> **username_2**: @username_1: I think that we can count the number of occurrences as subsequences in polynomial time by dynamic programming, making it possible to use the subsequence itself as a certificate.  
> **username_3**: recently studied something vaguely similar. 3 problems that seem related such that a solution might use similar ideas. [longest repeated substring](http://en.wikipedia.org/wiki/Longest_repeated_substring_problem), [Longest common subsequence problem](http://en.wikipedia.org/wiki/Longest_common_subsequence_problem), [longest common substring problem](http://en.wikipedia.org/wiki/Longest_common_substring_problem). useful is the [suffix tree](http://en.wikipedia.org/wiki/Suffix_tree) or [generalized suffix tree](http://en.wikipedia.org/wiki/Generalised_suffix_tree)  
> **username_3**: re TIs comment, (1) can you sketch that out further? is it in P to count the occurences of a known subsequence? (2) dont see how knowing the total # occurrences of the subsequence proves that its the maximum. (but, probabilisticly, yeah, one could randomly sample other known subsequences and verify that its count is always larger than theirs.)  
> **username_2**: @username_3: What I meant is that the usual decision version (which Niel stated in his comment) is in NP.  It does not give a certificate for maximality, of course.  I do not think that your procedure is a correct probabilistic verification procedure for maximality in the sense of [MA](http://qwiki.stanford.edu/index.php/Complexity_Zoo:M#ma), if that is what you meant.  
> **username_3**: not claiming my sketch fits into any particular class, its just a probabilistic algorithm given a subroutine that can count the occurrences of a given subsequence. what exactly is the related/similar/"usual" NP version/problem? nobody seems to have pointed to any std NP problem so far...?  
> **username_2**: @username_3: I already answered your question in my previous reply to you.  Read Niel’s comment more carefully.  
> **username_4**: I'm a little confused: is the question "given a string s, find the subsequence that occurs the maximum number of times?"  
> **username_5**: @SureshVenkat: Yes, that's my understanding.  For example, given a sequence of $n$ X's as input, the correct answer would be a sequence of $n/2$ X's.  
> **username_6**: @username_0: [this question on stackoverflow seems the same](http://stackoverflow.com/questions/6877249/find-the-number-of-occurrences-of-a-subsequence-in-a-string) (see aioobe's good answer that uses dynamic programming).  
> **username_7**: @marzio-de-biasi: the question you linked to is different (and much easier): there you are given the subsequence.  
> **username_3**: lemma 3 of [this paper, algorithms for subsequence combinatorics by Elzinga et al](http://compalg.inf.elte.hu/~tony/Kutatas/PerfectArrays/Elzinga-AlgorithmsSubsequenceCombinatorics.pdf) looks close to me, it counts the k-long subsequences. maybe it can be modified without too much trouble to count each one of the k-long subsequences.  
> **username_8**: Is there a $c<1$, such that a shortest commonest subsequence has length at most $cn$? I made the conjecture with $\lceil \frac{n}{2}\rceil$, but here is a counterexample if my code was correct: The length 14 string $ababaaabbbabab$ has a shortest commonest subsequence of length 8, $abaabbab$. If there is such a $c$, then it would give us an algorithm at least a bit better than the naive $O(2^n)$ one.  

---

## 2 answers

### Answer by username_3 on 2012-08-28. Score: 5

from a search, here is a paper with some research & findings for graduate level research but (caveat) no references. it has some heuristics, estimates, empirical results & commentary on the problem and some ideas on proving its (approximation) complexity etc.

[Identification of Most Frequent Subsequences](http://bautin.org/pdf/most_freq_subseq.pdf)  
CSE 549 Computational Biology Project Final Report  
Mikhail Bautin 2006

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

> **Comments:**
> **username_9**: I don't understand why this was downvoted. It may not be a very deep paper but it appears to be directly on topic.  
> **username_3**: fyi/addendum Bautin also says at the end of paper he has 5K lines of C++ & Python code on the problem/paper for anyone interested  
> **username_10**: @David, I don't think the downvote is because of the linked paper, it is probably more to do with the fact that this answer looks like (essentially) a one line link answer (without explaining how the paper is related to the question and answers it). This might have been more appropriate as a comment.  
> **username_3**: ok kaveh, then, spelled out: the paper seems to reveal (unless anyone can find a better ref or come up with proof of this difficult problem themself) that _the exact complexity of the problem is so far unknown/open_ (other than the obvious PSpace/ExpTime) and _may contain the best known analysis/approaches to solving it so far_  
> **username_0**: I did find this paper before and apologize for not linking to it above, which was since I didn't think it gave much concrete information. I sent the author an email some time ago asking if there was any more he could say about anything that happened since it was written, but got no reply yet.  

---

### Answer by username_11 on 2012-08-26. Score: 3

Not an answer, just a lemma.

So first of all one might wonder what the commonest subsequence of strings like 12..t12..t12..t.. is. After a little thinking one realizes that it must also have the form 12..t12..t12.., just obviously shorter. If the original string has length nt, and the subsequence of this special form has length k, then the number of its occurrences is exactly ${n+k-\lceil k/t\rceil \choose k}={n+k-\lceil k/t\rceil \choose n-\lceil k/t\rceil}$. This implies that the most common subsequence also ends with $t$ (i.e. $k$ has to be divisible by $t$). But where does this take its maximum and how much is it??? Quite embarassing, but I could not figure it out...


---

