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$.
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
Your question is now, given $u$, to find a word $v$ such that $\binom{u}{v} = 2$.