Задача: 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) {
    let subsequencesCount = 0;
    let targetIndex = 0;

    while (targetIndex < target.length) {
        let sourceIndex = 0;
        subsequencesCount++;
        let startIndex = targetIndex;

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

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

    return subsequencesCount;
}

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