LeetCode in Kotlin

3983. Subsequence After One Replacement

Medium

You are given two strings s and t consisting of lowercase English letters.

You may choose at most one index in s and replace the character at that index with any lowercase English letter.

Return true if it is possible to make s a subsequence of t; otherwise, return false.

Example 1:

Input: s = “cat”, t = “chat”

Output: true

Explanation:

• Replace s[1] from 'a' to 'h'. The resulting string is "cht".
• "cht" is a subsequence of "chat" because we can match 'c', 'h', and 't' in order.

Example 2:

Input: s = “plane”, t = “apple”

Output: false

Explanation:

• The characters 'p', 'l', and 'e' can be matched in t, but the remaining characters cannot be matched while preserving the required order.
• Even after replacing any one character in s, it is impossible to make s a subsequence of t.

Constraints:

• 1 <= s.length, t.length <= 105
• s and t consist only of lowercase English letters.

Solution

import kotlin.math.max

class Solution {
    fun canMakeSubsequence(t: String, s: String): Boolean {
        val arrS = s.toCharArray()
        val arrT = t.toCharArray()
        if (arrS.size < arrT.size) {
            return false
        }
        var idx1 = 0
        var idx2 = 0
        val n = arrT.size
        for (curr in arrS) {
            var nextIdx1 = idx1
            var nextIdx2 = idx2
            if (idx2 < n && arrT[idx2] == curr) {
                nextIdx2 = max(nextIdx2, idx2 + 1)
            }
            if (idx1 < n) {
                nextIdx2 = max(nextIdx2, idx1 + 1)
            }
            if (idx1 < n && arrT[idx1] == curr) {
                nextIdx1 = idx1 + 1
            }
            nextIdx2 = max(nextIdx2, nextIdx1)
            idx1 = nextIdx1
            idx2 = nextIdx2
        }
        return idx1 == n || idx2 == n
    }
}

This site is open source. Improve this page.