Is Subsequence

Условие

Даны две строки s и t, нужно определить, является ли s подпоследовательностью t. Подпоследовательность — это строка, полученная путем удаления некоторых (возможно, ни одного) символов из другой строки без изменения порядка оставшихся символов.

Примеры

Input: s = “abc”, t = “ahbgdc”

Output: true

Input: s = “axc”, t = “ahbgdc”

Output: false

Решение

fun isSubsequence(s: String, t: String): Boolean {
    var sIndex = 0
    var tIndex = 0

    // Проходим по строке t, проверяя, присутствуют ли все символы строки s в правильном порядке
    while (sIndex < s.length && tIndex < t.length) {
        if (s[sIndex] == t[tIndex]) {
            sIndex++  // Переходим к следующему символу в s, если текущий символ совпал
        }
        tIndex++  // Переходим к следующему символу в t в любом случае
    }

    return sIndex == s.length  // Если прошли всю строку s, значит, она является подпоследовательностью
}

Временная сложность

O(n + m), где n — длина строки s, а m — длина строки t, так как мы проходим по каждой строке один раз.

Пространственная сложность

O(1), так как не используется дополнительная память, зависящая от размера входных данных.