Задача: 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.

😎 Решение:

func minSubsequences(_ source: String, _ target: String) -> Int {
    let sourceArray = Array(source)
    let targetArray = Array(target)
    var subsequencesCount = 0
    var targetIndex = 0

    while targetIndex < targetArray.count {
        var sourceIndex = 0
        subsequencesCount += 1
        let startIndex = targetIndex

        while sourceIndex < sourceArray.count && targetIndex < targetArray.count {
            if sourceArray[sourceIndex] == targetArray[targetIndex] {
                targetIndex += 1
            }
            sourceIndex += 1
        }

        if targetIndex == startIndex {
            return -1
        }
    }

    return subsequencesCount
}

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