5455. Число различных подпоследовательностей

Даны строки s и t. Нужно получить t из s, вычёркивая любые буквы, но не переставляя оставшиеся.

Считать нужно не «получается / нет», а сколько разных способов вычеркнуть. Два способа различны, если отличаются наборы позиций оставшихся букв — даже когда сами буквы совпадают. Буквы t в s не обязаны стоять рядом: между ними можно вычеркнуть сколько угодно символов.

Если t пустая — ровно 1 способ: вычеркнуть всё (в том числе из пустой s). Если t непустая, а s пустая — 0.

Верните число способов.

s = rabbbit
позиция|  0|  1|  2|  3|  4|  5|  6|
буква  |  r|  a|  b|  b|  b|  i|  t|
t = rabbit     нужны r, a, две b, i, t

букв b в s три (позиции 2, 3, 4), в t нужны две.
остальные буквы в s по одной — выбора нет.
три способа выбрать две b из трёх:

  позиции  0,1,2,3,5,6    взяли b на 2 и 3
  позиции  0,1,2,4,5,6    взяли b на 2 и 4
  позиции  0,1,3,4,5,6    взяли b на 3 и 4

ответ 3

Второй пример — все разные наборы позиций выписываются явно:

s = babgbag
позиция|  0|  1|  2|  3|  4|  5|  6|
буква  |  b|  a|  b|  g|  b|  a|  g|
t = bag

нужна тройка позиций i < j < k, где s[i]=b, s[j]=a, s[k]=g.
буквы b на 0,2,4;  a на 1,5;  g на 3,6.
индексы обязаны расти, поэтому «назад» к букве слева нельзя:

  (0, 1, 3)    b a g
  (0, 1, 6)    b a g
  (0, 5, 6)    b a g
  (2, 5, 6)    b a g     после b на 2 буква a слева (позиция 1) уже недоступна
  (4, 5, 6)    b a g     последние три буквы подряд — тоже подходит

ровно 5 троек, ответ 5