We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
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.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Append and Delete
You are viewing a single comment's thread. Return to all 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 appendt.size()
characters (s.size() + t.size() = L
steps in total). However, since we have a prefix of lengthi
, we can skipi
deletions andi
additions. Therefore, we need at leastL - 2*i
operations in total. Ifk
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 tok%2 == L%2
), we can first doL - 2*i
operations to get the stringt
, and then just append a character and immediately remove it. Since(k - (L - 2 * i)) % 2 == 0
means that the difference betweenk
andL - 2*i
is even, this is always possible.There is one more special case; since
remove("") == ""
, if we havek >= L
, we can just dos.size()
deletions, then anotherk - L
deletions, andt.size()
additions. In this special case, we can always find a way to converts
tot
usingk
operations.