Append and Delete - JavaScript

I recently realized I haven’t documented much since I started learning to code. I solved an algorithm on HackerRank yesterday and would like to write about that. I solved the algorithm using JavaScript.

The Problem

You have two strings in 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”.

Link to the problem: https://www.hackerrank.com/challenges/append-and-delete/problem

appendAndDelete( “aba”, “aba”, 7) should return “Yes”.

appendAndDelete( “y”, “yu”, 7) should return “No”.

Heads up, an empty string can be deleted (and will still leave the string empty) and all moves MUST be exhausted. These were the two things I struggled the most with while solving the algorithm.

My Idea

There are a list of things I would need to know to solve the algorithm.

1. The number of consecutive letters shared by string s and string t. This is to know the number of letters I wouldn’t necessarily have to use moves to remove or add.
2. The number of unique letters in string s and string t each. This is to know the number of letters I would need to remove and add in string s.
3. The number of moves left after removing the unnecessary letters from string s and adding the necessary letters. This is to know if string s can be completely erased and replaced with k number of moves. If not, to know if the number of moves left is an even or odd number. The purpose of this is to know whether the moves can be exhausted by deleting an empty string or removing a letter and replacing it over and over again.
4. Creating a condition to check if the remaining moves cannot be wasted. This checks for two things. One, if the moves are enough to completely erase the string and replace it correctly; in this case, extra moves can be wasted by deleting an empty string. Two, if the moves remaining after removing unnecessary letters is even or odd. Even numbers will allow deleting and replacing letters even when string s is complete, while odd numbers will be exhausted while string s is incomplete if there is an attempt to waste extra moves in the same way.
5. Creating a condition to return “Yes” if there are enough moves to remove unnecessary letters from string s and add necessary letters to string s. There should be no need to worry about extra moves left because the first condition would have handled it and in cases that reached this condition, “Yes” should be returned.
6. Creating a condition to return “No” for everything else. The cases here would be cases with too few moves to remove the unnecessary letters from string s and add the necessary letters afterwards.

My Solution

Knowing the number of consecutive letters shared by string s and string t.

The way I thought to begin was to first figure out how many letters were similar. So if s = “hackerrank” and t = “hackerhappy”, I would need to first know how many letters I could leave as they were. That would be six in this case, the six letters in “hacker”. To do this, I created a for loop and split s and t into arrays. I created a variable, count = 0, where count represented how many letters the two strings shared. I let the loop continue to run as long as sArr[i] === tArr[i]. Each time it ran, the count was incremented by 1. I ran into an error in some test cases in which string s and string t had the same values. This was because it created an infinite loop where the condition was never met, as sArr[i] === tArr[i] would always return true where the values are the same. I added another condition to the for loop to solve this, that the loop should also only continue to run as long as i < s.length.

let sArr = s.split("")
    let tArr = t.split("")
    let count = 0
    for (let i = 0; i === count && i < s.length; i++) {
        if (sArr[i] === tArr[i]) {
            count++
        }
    }

Knowing the number of unique letters in s and t each.

Next, after figuring out the number of similar strings I could leave between string s and string t, I needed to figure out the number of strings I needed to alter. I first tried to return “Yes” as long as the numbers left in string s were less than or equal to k / 2. This seemed to make sense. If s = “qwerasdf”, t = “qwerbsdf”, and k = 8, I would need 8 (k) moves. I would need four moves to remove the wrong letters and four moves to add the right letters. However, there were two situations my method did not consider. One, if string s and string t are different lengths. That would mean the number of letters I would need to append to string s wouldn’t be the same as the number of letters I would need to remove. Second, it didn’t consider situations where the moves wouldn’t be exhausted exactly as string s and string t match. Take for example, turning “y” to “yu”. I would need only one move for that, yet my tests would have passed at k = 2. However, after adding “u” to “y”, I would need to use the last move. This meant that the test should have returned “No”.

To solve this, I created variables to hold what was left in length after subtracting “count” from both s.length and t.length.

let tMinusCount = t.length - count
let sMinusCount = s.length - count

Knowing the number of moves left after string s becomes string t.

I used the variable STK to hold this value, where STK = k — (tMinusCount + sMinusCount). I needed to know this value for situations where the k number of moves would not be exhausted exactly as s was converted to t. If s = “y”, t = “yu”, and k = 2, s would be t in a single move by adding “u” to “y”. However, the algorithm required me to exhaust the moves completely. So I needed to know if what was left would be enough to append and delete until the moves were exhausted. In the example above, it would not be because only one move was left. Appending or deleting anything with one move ends it, so it would need to return “No”. This is the case for every odd number. With even numbers, a letter can be removed and added back until the moves are exhausted.

let STK = k - (tMinusCount + sMinusCount)

The first conditional statement.

The first conditional statement checks if the extra moves that may be left after s becomes t can be wasted. The first condition checks if tMinusCount + sMinusCount is less than k. If tMinusCount + sMinusCount === k, then there would be no extra moves and there would be no need to run the code within the condition. If it was greater than k, then there would be no extra moves either. The second condition checked if t.length + s.length > k. If it was less than k, there would be no need for the function to run, as there would be enough moves to delete all of the letters to an empty string, waste whatever moves are necessary, and then add the necessary letters. It would be irrelevant that the number of remaining letters would be an odd or even number. The last condition checked if the remaining moves to be wasted was an odd or even number. If it was an odd number, and the other two conditions were met, the function returned “No”. If not, the function would continue to run.

if (tMinusCount + sMinusCount < k && t.length + s.length > k && STK % 2 !== 0) {
        return "No"
    }

The second conditional statement.

The second conditional statement had a single condition. If tMinusCount + sMinusCount <= k, the function should return “Yes”. If the condition was passed, it would mean that there were enough moves to remove the unnecessary letters from string s and add the necessary letters. sMinusCount is the number of unnecessary letters to be removed (unique to string s and needed to be removed from string s). tMinusCount is the number of necessary letters to be added (unique to string t and needed to be added to string s). Every other case should return “No”. The initial if statement already addresses cases with extra moves. Every other set of values that reach the “else” point would have tMinusCount + sMinusCount > k. That would mean that there wouldn’t be enough moves to remove the unnecessary letters from string t and add the necessary letters. In this case, the function should return “No”.

else if (tMinusCount + sMinusCount <= k) {
        return "Yes"
    }

This is the final result:

function appendAndDelete(s, t, k) {
    let sArr = s.split("")
    let tArr = t.split("")
    let count = 0
    for (let i = 0; i === count && i < s.length; i++) {
        if (sArr[i] === tArr[i]) {
            count++
        }
    }

    let tMinusCount = t.length - count
    let sMinusCount = s.length - count

    let STK = k - (tMinusCount + sMinusCount)

    if (tMinusCount + sMinusCount < k && t.length + s.length > k && STK % 2 !== 0) {
        return "No"
    } else if (tMinusCount + sMinusCount <= k) {
        return "Yes"
    } else {
        return "No"
    }
}

If you have a more readable or faster solution, or any different solution at all, please share.