Delete Consecutive Same Words In A Sequence Of Words Using Stack In C++

In this article, we will address the problem of identifying and removing consecutive similar words from a sequence of strings using C++. We will walk you through the algorithm and provide a sample C++ code to implement this solution.

Problem Statement

Given a sequence of n strings, the task is to check if any two similar words come together and then destroy each other then print the number of words left in the sequence after this pairwise destruction.

Algorithm Overview

In this solution we are using Stack data structure.

• Create an empty stack to store words.
• Initialize a variable ‘count’ to 0 to keep track of the number of words left.
• Iterate through each word in the input sequence:
  • If the stack is not empty and the current word is equal to the word at the top of the stack, it indicates a pair of similar words. Pop the word from the stack (destroy it) and continue to the next word.
  • If the stack is empty or the current word is different from the word at the top of the stack, push the current word onto the stack to preserve it.
• After processing all the words in the sequence, the stack will contain the remaining words that survived destruction.
• The size of the stack at this point represents the number of words left.
• Return the value of ‘count’ as the result.

Implementation in C++

#include<bits/stdc++.h>
using namespace std;

int removeConsecutiveSame(vector<string> inputSequence) {
    int sequenceSize = inputSequence.size();
    for (int i = 0; i < sequenceSize - 1;) {
        if (inputSequence[i] == inputSequence[i + 1]) {
            inputSequence.erase(inputSequence.begin() + i);
            inputSequence.erase(inputSequence.begin() + i);
            if (i > 0) {
                i--;
            }
            sequenceSize -= 2;
        } else {
            i++;
        }
    }
    return inputSequence.size();
}

int main() {
    vector<string> inputSequence = { "ab", "aa", "aa", "bcd", "ab" };
    cout << "Number of words left: " << removeConsecutiveSame(inputSequence) << endl;
    return 0;
}

Conclusion

In solving this problem, we have utilized a stack data structure to efficiently identify and remove consecutive similar words from a sequence of strings. The algorithm preserves non-consecutive words while eliminating consecutive duplicates, ultimately yielding the count of words remaining in the sequence as the result.