Removing duplicate adjacent items from a string - what's wrong with my function/conditionals?

Hello :slight_smile:

I patched together the below code to solve one of leetcode’s problems. Whenever I try fiddling with the code and getting it to work for one test case, another case breaks it. The only thing I’ve found that works is to call the checkDupes() function four times - but I can’t see why (with my foundDupe boolean to check), one calling of the function isn’t enough.

(I realise that this only works because it “beats the system” - it only passed the specific, limited test cases that were used).

So the problem is here:
https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string/

Given a string S of lowercase letters, a duplicate removal consists of choosing two adjacent and equal letters, and removing them.

We repeatedly make duplicate removals on S until we no longer can.

Return the final string after all such duplicate removals have been made. It is guaranteed the answer is unique.

these are three of the string test cases they provide:

“abbaca”
“aaaaaaaaaa”
“ibfjcaffccadidiaidchakchchcahabhibdcejkdkfbaeeaecdjhajbkfebebfea”

and this is the code I used:

var removeDuplicates = function(S) {

    var SArray = S.split("");
    var foundDupe = false;    

    function checkDupes() {
        for (var i = 0; i < SArray.length; i++) {
            if (SArray[i]==SArray[i+1]) {
                SArray.splice(i,2);
                foundDupe = true;
            }
        }
    }
    
    checkDupes();

    if (foundDupe==true) {
        checkDupes();          
        checkDupes();          
        checkDupes();          
        checkDupes();      
    }

    S = SArray.join("");    
    return S;
};

I am still working a solution. From what I gathered, you have to call checkDupes multiple times.

lets take this string as example:

abbaca

after calling checkDupes on this string, the succesive bb have been removed so we end up with:

aaca

so due to the removal we now formed new successive vowels (aa), so every time duplicates are found, you should loop again

so you might want to replace the 4 calls with some kind of loop. Best with what I can come up with for now

what I initially wanted to do is to have the foundDupe boolean determine whether to run the function again (and loop again if foundDupe is set to true), but I couldn’t figure out at which point to set it to false (once there are no duplicates) that didn’t result in an incomplete splicing or unfinished loop and duplicates remaining.

In the current code foundDupe is set to true once the first duplicate is found and then doesn’t get changed anywhere…

you could set foundDupes to false within the checkDupes function:

function checkDupes() {
   let foundDupe = false;

then add the end of the function return foundDupe. If duplicates are found, somewhere in the loop, foundDupe has been set to true, otherwise it remains false.

i’ve just tried adding that line to set it to false and also returning it, but it still doesn’t accept the test case if I then remove the four function calls and have only one. That’s with this test string:

“ibfjcaffccadidiaidchakchchcahabhibdcejkdkfbaeeaecdjhajbkfebebfea”

can i see your full code? Was that test case working with the 4 function calls?

that code block in my first post is the full code. You start off with a blank removeDuplicates function and have to code the function so that the S passed into it gets its duplicates removed - you don’t have access to the different S strings that they use to evaluate your code, but you could technically just add the test code before that function:

var S = “ibfjcaffccadidiaidchakchchcahabhibdcejkdkfbaeeaecdjhajbkfebebfea”;

But that code work? And did you replace the multiple calls with a loop? And if so, how? Please post your full code again.

the code in the first post works with that test case. I’ve also just discovered that I can remove the if conditional at the end and it still works - so no if is needed to check the boolean, but still multiple function calls.

I don’t know hey…I’ve tried loops there, even with looping for the length of a very large test case, but as before, doing that just results in a wrong answer.

A for loop instead of the five function calls has a problem with “aaaaaaaaaa” as a test case (it leaves two “aa” and doesn’t slice them out.

I would approach this in parts:

  1. How to identify a duplicate
  2. How to get rid of that duplicate
  3. How to loop over the same test case until you are done
  1. How to identify a duplicate

if (SArray[i]==SArray[i+1]) {

  1. How to get rid of that duplicate

SArray.splice(i,2);

  1. How to loop over the same test case until you are done

if (foundDupe==true) {
checkDupes();
checkDupes();
checkDupes();
checkDupes();
}

:upside_down_face: :rofl: that’s where the problem lies, I can’t figure out a conditional or toggling boolean or for loop that correctly stops when done - other than pasting in more checkDupes to outmuscle the wave of test cases.

You could use a while(condition) loop to remove dupes until there are no more. I modified your code a little and it seems to work but is maybe not the most efficient solution.

var removeDuplicates = function(S) {
var SArray = S.split("");

const removeDupes = () => {
    for (let i = 0; i < (SArray.length - 1); i++) {

            if (SArray[i] === SArray[i+1]) {
                SArray.splice(i, 2)
                return true;
            }
        };
    return false;
}

while(removeDupes()) {
};

const filteredString = SArray.join("");
return filteredString;

};

ah, great stuff! yes, your code works - I’m sure there far better and more efficient solutions to this coding problem, as my (your!) solution ranks quite slow compared to other users’ submissions, but it’s a great way to get my head around the basics and get them right before going onto more advanced stuff. Thanks a bunch for the input!

Easy - don’t use a loop.

Your first pass of the function will either:

  1. Find a duplicate, in which case you need to remove it,

    or

  2. Find no duplicates, in which case you need to return the original string.

The while loop seems the obvious approach, because it’s what you’re taught to think of when you need to repeat an action for an unknown number of iterations.

What you may not have considered, however, is that you can use a recursive program.

Whenever you find a duplicated character, remove it. Then, pass the new shortened string back in to the same function to check that new string for dupes. Continue until there are no more dupes, and return the result. :slight_smile:

I think that might have been the problem in the original code - that the array length changes as items are removed but using that loop it goes with the original length and not the new length maybe?

Take a look at my solution and see if it makes sense to you: https://repl.it/@fedGL/leetcodeRemoveDuplicates

1 Like