Почему это работает
- Взять первую подходящую букву t никогда не хуже, чем более позднюю: всё, что поместится после поздней, поместится и после ранней — после неё t осталось больше.
- Буква t, которая не равна искомой, не пригодится и потом: следующие буквы s должны стоять после текущей, а эта буква — раньше неё.
- Если i дошёл до конца s, все буквы нашлись по порядку: да. Если раньше кончилась t, какой-то букве s не нашлось места после предыдущих: нет.
Сложность
Время O(n), где n — длина t: j сдвигается на букву каждый шаг, поэтому цикл идёт не больше n раз. Память O(1): только два индекса.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗