Ctrl K

Различные подпоследовательности

Сложная
Подпоследовательность строки получается вычёркиванием некоторых её символов (возможно, ни одного) без изменения порядка остальных. Например, "ace" — подпоследовательность "abcde", а "aec" — нет. Дана строка letters. Посчитайте, сколько **различных непустых** строк можно получить как её подпоследовательности. Ответ может быть очень большим — верните его по модулю 10⁹ + 7.
Пример 1
letters="xyz" → 7

Все 7 непустых подпоследовательностей разные: x, y, z, xy, xz, yz, xyz.

Пример 2
letters="pop" → 6

Различные: p, o, po, pp, op, pop — всего 6 (вариант «p» получается двумя способами, но считается один раз).

Пример 3
letters="bbbb" → 4
Ограничения
  • 1 ≤ len(letters) ≤ 2000
  • letters состоит из строчных латинских букв
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиШаблон с точкой и звёздочкой СложнаяСамый длинный сбалансированный отрезок скобок СложнаяПодходит ли строка под шаблон СложнаяПеретасовка разрезами СложнаяСколькими способами вычеркнуть Сложная
загружаем Python…
Вход
letters="xyz"
Ожидается
7

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 56 тестов на сервере, включая скрытые.