LeetCode Entry

2486. Append Characters to String to Make Subsequence

03.06.2024 medium 2024 kotlin rust

Min diff to make t substring of s

2486. Append Characters to String to Make Subsequence medium blog post substack youtube 2024-06-03_09-03_1.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/627

Problem TLDR

Min diff to make t substring of s #medium

Intuition

Try to first solve it with bare hands: take the s string and walk over the chars, simultaneously adjusting the t char position:

s        t
abcccccd abdd
i      . j
 i     .  j
  i    .  j
   i   .  j
    i  .  j
     i .  j
      i.  j
       i   j

Looking at this example, the algorithm is clear: search for the next t[j] char in s.

Approach

  • save three lines of code with getOrNull ?: return in Kotlin
  • walking over bytes is only valid for ascii chars (Rust)

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(1)\)

Code


    fun appendCharacters(s: String, t: String): Int {
        var j = 0
        for (c in s) if (c == t.getOrNull(j) ?: return 0) j++
        return t.length - j
    }



    pub fn append_characters(s: String, t: String) -> i32 {
        let mut tb = t.bytes().peekable();
        t.len() as i32 - s.bytes().map(|b| {
            (b == tb.next_if_eq(&b).unwrap_or(0)) as i32
        }).sum::<i32>()
    }