Задача: 1055. Shortest Way to Form String
Сложность: medium

Подпоследовательность строки - это новая строка, которая образуется из исходной строки путем удаления некоторых (можно ни одного) символов без нарушения взаимного расположения оставшихся символов. (например, "ace" является подпоследовательностью "abcde", а "aec" - нет). Если даны две строки source и target, верните минимальное количество подпоследовательностей source, чтобы их объединение равнялось target. Если задача невыполнима, верните -1.

Пример:

Input: source = "abc", target = "abcbc"
Output: 2

👨‍💻 Алгоритм:

1⃣Используй два указателя для отслеживания текущих позиций в строках source и target.

2⃣Перебирай символы строки source, пока не найдешь совпадающий символ в target.
Если ты прошел всю строку source и не нашел все символы target, увеличь счетчик количества подпоследовательностей и начни снова с начала source.

3⃣Повтори шаги 2 и 3 до тех пор, пока не пройдешь всю строку target.

😎 Решение:

function minSubsequences($source, $target) {
    $subsequencesCount = 0;
    $targetIndex = 0;

    while ($targetIndex < strlen($target)) {
        $sourceIndex = 0;
        $subsequencesCount++;
        $startIndex = $targetIndex;

        while ($sourceIndex < strlen($source) && $targetIndex < strlen($target)) {
            if ($source[$sourceIndex] === $target[$targetIndex]) {
                $targetIndex++;
            }
            $sourceIndex++;
        }

        if ($targetIndex === $startIndex) {
            return -1;
        }
    }

    return $subsequencesCount;
}

Ставь 👍 и забирай 📚 Базу знаний