TITLE: Subsequence occurring exactly twice in pattern
QUESTION [1 upvotes]: Given a string $S$, consisting of letters from the set $\{0, 1\}$. We need to find a string $T$ that appears in $S$ as a subsequence exactly twice.
How to tackle this problem, without enumerating all subsequences.
Max value of $N$ is $5000$.
Example : In string $S= 101$ answer is $1$ as it appear exactly twice. How to do it for given string $S$.

REPLY [1 votes]: As your question is part of an ongoing programming contest, I will not answer it but rather give you some related mathematical background. I let you check whether this information is useful or not for your precise problem.
A word $u$ is a subword of $v$ if $v$ can be written as 
$v = v_0u_1v_1u_2v_2\dotsm u_kv_k$
where $u_i$ and $v_i$ are (possibly empty) words such that $u_1u_2\dotsm u_k = u$. For instance, the words $\color{red}{baba}$ and $\color{red}{acab}$ are subwords of $abcacbab$ since
$abcacbab = a\color{red}{b}c\color{red}{a}c\color{red}{ba}b = \color{red}{a}b\color{red}{ca}c\color{red}{b}ab$.
Now, given two words $u$ and $v$ the binomial coefficient $\binom{u}{v}$ is defined as follows
$$
 \binom{v}{u} = \left| \left\{ (v_0, \ldots,v_n) \mid v
 = v_0a_1v_1 \ldots a_nv_n \right\} \right|.
$$
Observe that if $a$ is a letter, then $\binom{v}{a}$ is simply the number
of occurrences of $a$ in $v$, also denoted by $|v|_a$. Also note
that if $A = \{a\}$, $u = a^n$ and $v = a^m$, then
$$
 \binom{v}{u} = \binom{m}{n}
$$ 
and hence these numbers constitute a generalization of the classical
binomial coefficients. The generalized binomial coefficients can be iteratively computed using the following generalisation of Pascal's triangle. Let $1$ be the empty word. Let $u,v \in A^*$ and $a,b \in A$. Then

$\binom{u}{1} = 1$,
$\binom{u}{v} = 0$ if $|u| \leqslant |v|$ and $u \neq v$,
$\binom{ua}{vb} = \begin{cases}
  \binom{u}{vb}                &\text{if $a\not= b$}\\
  \binom{u}{vb} + \binom{u}{v} &\text{if $a= b$}
 \end{cases}$

Your question is now, given $u$, to find a word $v$ such that $\binom{u}{v} = 2$.
{"set_name": "stack_exchange", "score": 1, "question_id": 1714397}