The Append and Delete Algorithm

In this article, I'll be describing how I solved the Append and Delete Challenge on HackerRank using Python 3.

This challenge is part of the Implementation challenges in the Algorithm section on HackerRank.

If this is your first time reading my data structures and algorithms article, consider reading more in my Algos in Plain English series.😃

Problem 🎲

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

1. Append a lowercase English letter to the end of the string.

2. Delete the last character of 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.

Example

s = [a, b, c]
t = [d, e, f]
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. Return Yes.

If there were 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.

Function Description

Complete the appendAndDelete function in the editor below. It should return a string, either Yes or No.

appendAndDelete has the following parameter(s):

• string s: the initial string

• string t: the desired string

• int k: the exact number of operations that must be performed

Returns

• string: either Yes or No

Check out the original challenge on HackerRank for more info on input constraints and other sample inputs.

Solution 🔧

In plain English, we are asked to change a word, s, into another word, t. We can make this change by either adding or deleting characters from s. adding a character is one opeation and deleting is another.

Given a fixed number of operations, k, we need to figure out if its possible to make the change from s to t with the exact k operations.

Details in the problem statement above.

In my original submission, I passed all but 1 test case and while trying to fix the algorithm, I found myself working backwards from the failed test case, but alas, this method would not end well as making one test case pass caused others that passed previously to fail.

After getting help from the discussion forums, I discovered the logic for slicing the words was incomplete in addition to not covering all test cases with my original conditional logic.

So let's get to it.

# First thing is to split both words (s and t) at a position such
# that their characters are no longer the same.
# Once we get this 'split index', we can check the remaining 
# characters or length of the words against a set of conditions
# that cover all test cases.

Step 1️⃣: Start by splittings and t.

We need to first split the words to know what's left of them before the appending/deleting operations begin.

1. We'll iterate over characters in s and t to find an index position where the characters in both words begin to differ.

2. We'll call this the split index, from which we can get the remaining characters after the split.

def appendAndDelete(s, t, k):
    # * let's call this the split index.
    i = 0

    # * Before running out of characters in both s and t and,
    # * while the characters in both words are the same...
    # * increment our split index, i by 1.
    while i < len(s) and i < len(t) and s[i]==t[i]:
        i += 1

    # * Get the remaining characters after splitting both words.
    remaining_chars_in_s = len(s[i:])   
    remaining_chars_in_t = len(t[i:])

Step 2️⃣: Develop conditional statements for all possible cases👨🏾‍💻

1. After we have gotten the remaining characters for both words after the split, we check the number of these characters against the number of operations in the first 2 conditional statements.

2. For cases when we can not split the words or for very large values of k, we check 2 more conditions .

3. And if all these conditions are not met, we simply return No.

    # the operations start after we have splitted the words,
    # i.e. from each word, we have the remaining word (or character) 
    # that need to be either appended onto or deleted.

    # if we have remaining characters exceeding the exact number of 
    # operations we can perform, it means there aren't enough 
    # opeations to turn s into t.
    # e.g. s = 'qwerasdf'
    #      t = 'qwerbsdf'
    #      k = 6
    if remaining_chars_in_s + remaining_chars_in_t > k:
        return 'No'

    # if the sum of remaining characters is the same as the number of
    # opeations, then we know it is possible to turn s to t. 
    # e.g. s = 'hackerhappy'
    #      t = 'hackerrank'
    #      k = 9
    elif remaining_chars_in_s + remaining_chars_in_t == k:
        return 'Yes'

    # assuming s and t are different and we can't split them,
    # if the sum of both words combined is less than or equal to 
    # the number of operations, it means all operations can be done
    # within k.
    # e.g. s = 'qwerty'
    #      t = 'zxcvbn'
    #      k = 100
    elif (len(s) + len(t)) <= k:
        return 'Yes'

    # assuming all of s is contained in t or vice verca, 
    # after slicing, we'll have extra characters in t or s. 
    # To know if these extra characters can be added (from t) or 
    # deleted (from s) completely, we use % 2. 

    # if it returns a remainder, it means there'll be an extra 
    # character after all operations have been used.

    # the [abs] just handles extra characters in eithe s or t.
    # * e.g. s = 'zzzzz'
    # *      t = 'zzzzzzz'
    #      k = 4
    elif abs(len(s) + len(t) - k) % 2 == 0:
        return 'Yes'

    # if all above fail.
    else:
        return 'No'

Lots of comments this time to drive home the point.😅

Full code:

def appendAndDelete(s, t, k):
    # Write your code here
    i = 0

    while i < len(s) and i < len(t) and s[i]==t[i]:
        i += 1

    remaining_chars_in_s = len(s[i:])  
    remaining_chars_in_t = len(t[i:])  

    if remaining_chars_in_s + remaining_chars_in_t > k:
        return 'No'
    elif remaining_chars_in_s + remaining_chars_in_t == k:
        return 'Yes'
    elif (len(s) + len(t)) <= k:
        return 'Yes'

    elif abs(len(s) + len(t) - k) % 2 == 0:
        return 'Yes'
    else:
        return 'No'

This is just one of many ways to solve this challenge.

That's it! Thanks for reading! 🙂

Hope this article helped with understanding this challenge. Happy Coding!👨🏽‍💻

Nonsocchi🥷🏽