Count the unique subsequences
Let the given string be $S$.  For a string $T$ that appears as a subsequence of $S$, we say that the list of positions $(x_1, \dots, x_{|T|})$ is an appearance of $T$ in $S$ if $S[x_1]S[x_2]\dots S[x_{|T|}] = T$.  The leftmost appearance of $T$ in $S$ is the unique one for which each position is minimal over corresponding positions in all appearances -- that is, $X$ is the leftmost appearance of $T$ in $S$ iff for all $1 \le i \le |T|$ and all appearances $Y$ of $T$ in $S$, $X[i] \le Y[i]$.  This leftmost appearance can be calculated with a simple greedy algorithm in which we loop through the characters of $T$, pairing each with the next available matching character in $S$.  Define $L(T)$ to be the last (rightmost) position in the leftmost appearance of $T$ in $S$.

Example: $S = abbaba$, $T = ba$.  The appearances of $T$ in $S$ are $(2, 4), (2, 6), (3, 4), (3, 6)$ and $(5, 6)$.  The unique leftmost appearance is $(2, 4)$, so $L(T) = 4$.

We say a subsequence $T$ of $S$ requires position $i$ of $S$ iff $L(T) = i$.  What this means is that $T$ is not a subsequence of $S[1 \dots i-1]$ -- the only ways to produce $T$ from $S$ involve including either the character at position $i$ in $S$, or some identical character further to the right.  The important thing to notice is that any subsequence $T$ of $S$ requires a unique position: the one given by by $L(T)$.  So if for each $1 \le i \le |S|$ we can count the number of subsequences of $T$ that require $i$, we can add these all up to obtain the total number of unique subsequences of $S$.

Let $r(i)$ be the number of subsequences of $S$ that require position $i$.  We can compute $r(i)$ by counting the total number of subsequences of $S$ that include position $i$ and end there, and then subtracting off the number of these subsequences that don't require $i$.  Calculating the number of subsequences that end at $i$ but don't require it is surprisingly easy to do, thanks to the following observation:


For every $1 \le j &lt; i$ such that $S[j] = S[i]$, every subsequence that requires $j$ can be turned into an appearance of the same subsequence that ends at $i$ but doesn't require $i$ -- and there are no other subsequences that end at $i$ but don't require it.  (Specifically, we could remove the final character (taken from position $j$ of $S$) and append position $i$, and the appearance formed this way yields the same subsequence.)


So we have $r(i) = \sum_{1\le k&lt;i} r(k) - \sum_{1\le j&lt;i, S[j]=S[i]} r(j)$.

(The first summation is the number of subsequences we get by appending $S[i]$ to each of the unique subsequences we have already seen; the second subtracts off subsequences we have seen before.)

The first summation is easy to optimise: It's just a running total.  The second summation can also be optimised further by tracking, for each distinct character, the sum so far of unique subsequences ending with that character:


$r(0) \gets 1$
For $i$ from 1 to $|S|$:


$r(i) \gets t - u[S[i]]$
$t \gets t + r(i)$
$u[S[i]] \gets u[S[i]] + r(i)$



Summing $r(i)$ values as they are computed allows the answer to be computed in linear time.