• + 2 comments

    Sure.

    First, we try to find the minimum number of operations needed. For this, we check how large the largest common prefix of the two strings is; eg. if we have "hello" and "hellno", our largest common prefix is "hell". We compute the length of this prefix by for(i = 0; s[i] == t[i]; i++);.

    If we didn't have such a prefix, we'd have to first delete s.size() characters, then append t.size() characters (s.size() + t.size() = L steps in total). However, since we have a prefix of length i, we can skip i deletions and i additions. Therefore, we need at least L - 2*i operations in total. If k is smaller than that, we can return early. L <= k + i*2 checks this.

    Now, if (k - (L - 2 * i)) % 2 == 0 (which is equivalent to k%2 == L%2), we can first do L - 2*i operations to get the string t, and then just append a character and immediately remove it. Since (k - (L - 2 * i)) % 2 == 0 means that the difference between k and L - 2*i is even, this is always possible.

    There is one more special case; since remove("") == "", if we have k >= L, we can just do s.size() deletions, then another k - L deletions, and t.size() additions. In this special case, we can always find a way to convert s to t using k operations.