Given a string S consisting of lowercase letters, the deduplication operation selects two adjacent and identical letters and deletes them.

The deduplication operation is repeated on S until the deletion cannot continue.

Returns the final string after all deduplication operations have been completed. The answer is guaranteed to be unique.

Example:

Input: "abbaca" Output: "ca" Explanation: For example, in "abbaca", we can delete "bb" because the two letters are adjacent and identical, this is the only duplicate item that can be deleted at this time. Then we get the string "aaca", where only "aa" can be deduplicated, so the final string is "ca".Copy the code

Tip:

  • 1 <= S.length <= 20000
  • SContains only lowercase English letters.

Idea one

And they say, every time we find two adjacent duplicates, we can delete them. So we can move the pointer across the string from left to right to see if two adjacent characters are the same, and if they are, we can cut them off and move the pointer to the character before them. This makes the pointer hover over the new string until it points to the end of the string, indicating that all duplicates have been deleted.

/ * * *@param {string} S
 * @return {string}* /
var removeDuplicates = function(S) {
  let i = 1;
  while(i<S.length){
    if(S[i] === S[i-1]) {
      S = S.slice(0,i-1)+S.slice(i+1);
      i--;
    }
    else i++;
  }
  return S;
};
Copy the code

Note that in javascript, out-of-bounds Pointers return undefined, so you can use this feature for direct comparisons. Other languages may also consider boundaries.

Problem number two

There’s another, more elegant way to do it. Each character can be compared to the last character before it. In other words, we want to find the last character in the traversal first. A “first in, last out, last in, first out” data structure is obvious — the stack.

/ * * *@param {string} S
 * @return {string}* /
var removeDuplicates = function(S) {
  const result = [];
  for(let c of S) {
    c === result[result.length-1]? result.pop() : result.push(c); }return result.join(' ');
};
Copy the code

Each new character is compared to the character at the top of the stack, and if it’s equal, it’s discarded, and that’s what we’re doing.

conclusion

This problem is relatively simple, and there are many ways to solve it. But usually we need to have a clearer understanding of the basic data structure, often can use these features to find a more concise and elegant algorithm to solve the problem.

This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign