Оно

Заметим, что если какой-то отрезок входит в ответ, любой его подотрезок тоже входит в ответ. Обозначим за $$$r_i$$$ максимальную правую границу отрезка строки $$$s$$$, начинающегося с позиции $$$i$$$, который можно получить из символов строки $$$t$$$. Несложно заметить, что $$$r_i \le r_{i + 1}$$$. Найдем $$$r_0$$$, для этого, посчитаем количество вхождений каждого символа в строку $$$t$$$, и будем идти по строке $$$s$$$ слева направо, уменьшая счетчики встреченных символов, пока счетчик одного из символов не станет отрицательным. Теперь, что того, чтобы найти $$$r_1$$$, нужно передвинуть границу рассматриваемого отрезка вправо на $$$1$$$, для этого просто увеличим счетчик, соответствующий символу $$$s_0$$$, и снова будем двигать правую границу, пока счетчики неотрицательны. Будем продолжать так делать для всех $$$i$$$. Итоговое время работы — $$$O(n)$$$.