Append and Delete : HackerRank Solution in Python.

You have a string of lowercase English alphabetic letters. You can perform two types of operations on the string:

1. Append a lowercase English alphabetic letter to the end of the string.
2. Delete the last character in the string. Performing this operation on an empty string results in an empty string.

Given an integer, k, and two strings, s and t, determine whether or not you can convert s to t by performing exactly k of the above operations on s. If it’s possible, print Yes. Otherwise, print No.

For example strings s=[a,b,c] and t=[d,e,f] . Our number of moves, k=6 . To convert s to t , we first delete all of the characters in 3 moves. Next we add each of the characters of t in order. On the 6th move, you will have the matching string. If there had been more moves available, they could have been eliminated by performing multiple deletions on an empty string. If there were fewer than 6 moves, we would not have succeeded in creating the new string.

Solution in Python 3.

First, we will count the number of times characters in s and t are equal to each other until we come upon an occurrence where character in s that is not equal to it’s corresponding character in t. We will store the number of matched occurrences in a variable called matched_occurrences.

For example, if string, s = “hackerrank” and t=“hackerhappy” then matched_occurrences = 6 as s and t both have substring ”hacker”. we break out of the for loop when corresponding characters are unequal in this case s[6]!=t[6] i.e “r”!=”h”.

Next we will perform two checks,

1. If addition of the number of given moves i.e k and 2 x matched occurrences which equals to matched characters, (because if we multiply number of occurrences by 2 we will get total number of matching characters) is greater than or equal to total length of given strings i.e tot_len and if both total length and k have equal modulus of 2 i.e whether k and tot_len are either both are even or both are odd.

2. If total length i.e tot_len is less than ‘k’.

In this example, s=’asdfqwertyuighjkzxcvasdfqwertyuighjkzxcvasdfqwertyuighjkzxcvasdfqwertyuighjkzxcvasdfqwertyuighjkzxcv’ , t = ‘bsdfqwertyuighjkzxcvasdfqwertyuighjkzxcvasdfqwertyuighjkzxcvasdfqwertyuighjkzxcvasdfqwertyuighjkzxcv’ and k = 100.

It is not possible to convert s to t in 100 occurrences as there 0 matched occurrences before an occurrence where corresponding characters in given to strings are unequal, here the equation of 1st check is 2*matched_occurrences+k = 2*0+100 is less than total length which is 200. The above example also doesn’t fall in edge cases where total length itself is less than k.

If the total length is greater than or equal to sum of 2 * matched_occurences and k, it is not possible to convert s to t. (except in a few edge cases where total length itself is less than k).

Full solution:-