Stack: Delete consecutive same words in a sequence

Problem Statement:

You are given a array of strings.
You need to find the number of words after pairwise deletion.

Example:

Input: arr[] = [“pro”, “dev”, “hi”, “hi”, “dev”]
Output: 1

First iteration, delete “hi”, remain with [“pro”, “dev”, “dev”]

Second iteration, delete “dev” remain with [“pro”]

Hence solution is 1

Solution Explanation:

We will take help of stack to solve the issue.

Iterate through the array, then check if the top element of the stack matches the current word.

If they are the same, remove from the stack, else, push the word.

Time Complexity: O(n)
Space Complexity: O(n)

Code Solution

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

int solution(vector<string>& arr) 
{
    
    stack<string> stk;

    for (string &word : arr) 
    {
        
        if (!stk.empty() && stk.top() == word) 
        {

            stk.pop(); 
        } 
        else 
        {
            
            stk.push(word); 
        }
    }
    
    return stk.size();
}

int main() 
{
    
    vector<string> arr = {"pro", "dev", "hi", "hi", "dev"};

    cout << solution(arr) << endl;

    return 0;
}

Output

1