title: Count number of subsequences within a sequence with max allowed events in between
body: <p>Given a main sequence of events (e.g., <code>A-&gt;B-&gt;A-&gt;B-&gt;B</code>), a subsequence (<code>A-&gt;B</code>), and a max allowed events in between (<code>n</code>), I would like to count the number of subsequences (<code>N</code>) within the main sequence.</p>
  <p>For example,</p>
  <p><code>N=2</code> for <code>n=0</code> (First A -&gt; First B, Second A -&gt; Second B)</p>
  <p><code>N=3</code> for <code>n=1</code> (First A -&gt; First B, Second A -&gt; Second B, Second A -&gt; Third B)</p>
  <p><code>N=4</code> for <code>n=2</code> (First A -&gt; First B, Second A -&gt; Second B, Second A -&gt; Third B, First A -&gt; Second B)</p>
  <p><code>N=5</code> for <code>n=3</code> (First A -&gt; First B, Second A -&gt; Second B, Second A -&gt; Third B, First A -&gt; Second B, First A -&gt; Third B)</p>
  <p>Is there an efficient algorithm for this problem? The main sequence for my problem can be long and I have many subsequences to count for.</p>