-1
$\begingroup$

A subsequence of a word is obtained by dropping some letters from it. The letters that are dropped need not be consecutive. For instance, ba, bna and banaa are all subsequences of the word banana. We are interested in counting the number of distinct subsequences of a fixed length of a given word. For example, the word banana has 11 different subsequences of length 3: {aaa, aan, ana, ann, baa, ban, bna, bnn, naa, nan, nna}. Observe that the number of subsequences of length k of abcbbcaacaab that end in a ‘c’ is the same as the number of subsequences of length k−1 of abcbbcaa. In each of the following cases, you are given a word and a number N. You have to compute the number of different subsequences of length N of the given word. (a) tinnitus, 3 (b) gobbledygook, 4 (c) gargantuan, 5

$\endgroup$
  • 2
    $\begingroup$ Welcome on CS. What have you tried? $\endgroup$ – Yamar69 Oct 21 at 9:35
1
$\begingroup$

Let $\Sigma$ be your alphabet, and $w \in \Sigma^*$ be your word. Let $w_i$ be the word consisting of the first $i$ characters of $w$ (for $i \le 0$, $w_i$ is the empty word $\varepsilon$). For $c \in \Sigma$, let $S[i,k,c]$ be the number of subsequences of $w_i$ that end with character $c$ and have length $k$. Moreover, for a word $w'$, let $\ell_c(w')$ be the index (counting from $1$) of the last occurrence of character $c$ in $w'$, if any, and $\ell_c(w')=0$ otherwise.

Then, for any $c \in \Sigma$, you have

$$ S[i,1,c] = \begin{cases} 0 & \mbox{if } w_i \in ( \Sigma \setminus \{ c \})^* \\ 1 & \mbox{otherwise} \end{cases}, $$ notice, in particular, that the above formula implies that $S[i,1,c] = 0$ whenever $i \le 0$, as $w_i = \varepsilon \in ( \Sigma \setminus \{ c \})^*$. In fact, for $i\le 0$, we have: $S[i,k,c] = 0$ regardless of $c$ and $k \ge 1$.

For $i>0$ and $k > 1$, the property that is hinted in your questions implies that: $$ S[i,k,c] = \sum_{c' \in \Sigma} S[\ell_c(w_i)-1,k-1,c']. $$

Since all $\ell_c(w_i)$ can be precomputed in $O(|\Sigma| \cdot |w|)$ time, each of the $O(|\Sigma| \cdot |w| \cdot N)$ values $S[i,k,c]$ can be found in $O(|\Sigma|)$ time using above equations, and this immediately yields a dynamic programming algorithm with complexity $O(|\Sigma|^2 \cdot |w| \cdot N)$, where the quantity you're looking for is exactly: $$ \sum_{c \in \Sigma} S[|w|,N, c]. $$

By storing the quantities $\sum_{c \in \Sigma} S[i, k, c]$ as soon as all the entries $S[i, k, \cdot]$ are known you can compute each entry in constant time, improving the overall time complexity to $O(|\Sigma| \cdot |w| \cdot N)$.

EDIT

As an example let's compute the number of subsequences of length $3$ of the word $w=banana$. Here are the values of $S[i,1,c]$ for $i \ge 1$, where the $i$-th row from the top contains the values $S[i,1, \cdot]$ is is labeled with the $i$-th character of $w$, so that $w_i$ is the string consisting of the labels of the first $i$ rows. The values $S[\cdot ,1, c]$ are on the column labelled $c$. Essentially, $S[i,1,c]$ is $1$ if $w_i$ contains character $c$.

$$ \begin{array}{c|c|c|c|} i \backslash c & a & b & n \\ \hline b & 0 & 1 & 0 \\ \hline a & 1 & 1 & 0 \\ \hline n & 1 & 1 & 1 \\ \hline a & 1 & 1 & 1 \\ \hline n & 1 & 1 & 1 \\ \hline a & 1 & 1 & 1 \end{array} $$

Let's now compute the values $S[i,2,c]$. As an example, consider $S[5,2,a]$. Since the last occurrence of $a$ in $w_5 = banan$ is in position $4$, we have $\ell_a(w_5)=4$. Using the formula above we can write $S[5,2,a]$ as $$ S[5,2,a] = S[3,1,a] + S[3,1,b] + S[3,1,n] = 1 + 1 + 1 = 3. $$

Another example is $S[2,2,n]$, for which $\ell_n(w_2) = \ell_n(ba) = 0$ and: $$ S[2,2,n] = S[-1,1,a] + S[-1,1,b] + S[-1,1,n] = 0 + 0 + 0 = 0, $$ since $S[-1, 1, \cdot] = 0$. Repeating this process for all $i=1,\dots,6$ and $c \in \{a,b,n\}$ we obtain:

$$ \begin{array}{c|c|c|c|} i \backslash c & a & b & n \\ \hline b & 0 & 0 & 0 \\ \hline a & 1 & 0 & 0 \\ \hline n & 1 & 0 & 2 \\ \hline a & 3 & 0 & 2 \\ \hline n & 3 & 0 & 3 \\ \hline a & 3 & 0 & 3 \end{array} $$

We can finally consider the values $S[i,3,c]$. Since we only care about the sum $S[6,3,a] + S[6,3,b] + S[6,3,n]$, it suffices to compute these values. Notice that $$ \ell_a(w_6) = \ell_a(banana)= 6 \\ \ell_b(w_6) = \ell_b(banana)= 1 \\ \ell_n(w_6) = \ell_n(banana)= 5, $$
and hence we have:

$$ S[6,3,a] = S[5,2,a] + S[5,2,b] + S[5,2,n] = 3 + 0 + 3 = 6 \\ S[6,3,b] = S[0,2,a] + S[0,2,b] + S[0,2,n] = 0 + 0 + 0 = 0 \\ S[6,3,n] = S[4,2,a] + S[4,2,b] + S[4,2,c] = 3 + 0 + 2 = 5. $$.

I.e., the number of subsequences of length $3$ in $banana$ is $6 + 0 + 5 = 11$, which matches your example.

$\endgroup$
  • $\begingroup$ @anonymous downvoter, what's wrong with the answer? $\endgroup$ – Steven Oct 21 at 11:42
  • 1
    $\begingroup$ Perhaps it expresses dislike for solving the question although OP has shown no effort at all. Some people don’t like it, since often these are exercises that posters don’t feel like doing on their own, and so it’s a form of cheating. As somebody who often does it (though mostly for what I consider somewhat harder exercises), I can’t really complain. Another option is to present just the idea of the solution, and have the OP fill in the details. $\endgroup$ – Yuval Filmus Oct 21 at 14:42
  • 2
    $\begingroup$ On the other hand, a goal of the site is to have questions with good answers, which can be looked up. And that’s what we have now: A question and a good answer. If anyone else needs it, it’s here. $\endgroup$ – gnasher729 Oct 21 at 15:46
  • $\begingroup$ Could you explain how it works with example because I don't understand it that well because I have just started with such kind of problems. $\endgroup$ – Abhimanyu Singh Rathore Oct 22 at 16:41
  • $\begingroup$ I added an example. $\endgroup$ – Steven Oct 22 at 18:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.