Delete consecutive same words in a sequence

Table of Contents

Problem Statement

the problem “Delete consecutive same words in a sequence” states that you are given a list of n strings. If there are two same words present consecutively, delete both of them. Print the total number of words/strings left in the list after the deletion of all such pairs.

Delete consecutive same words in a sequence

Example

s[ ] = {ab, aa, aa, bcd, ab}

s[ ] = {cpp, cpp, java}

Using Stack

Algorithm

Initialize a list of n strings.
Create a stack data structure.
Traverse from 0 to size of the list – 1.
1. Check if the stack is empty i.e. the size of the stack is 0
  1. Push/insert the word at the current index in the list in the stack.
2. Else create a string variable and store the string at the top of the stack in it.
  1. Compare the string variable with the word at the current index in the list, if both the strings are the same.
    1. Remove the string from the top of stack.
  2. Else if the strings are different.
    1. Push the string at current index to the stack.
Return the size of the stack.

Code

C++ Program to delete consecutive same words in a sequence

#include<bits/stdc++.h> 
using namespace std; 
  
int removeConsSame(vector<string > s){ 
    stack<string> st; 
  
    for(int i=0; i<s.size(); i++){ 
        if(st.empty()){ 
            st.push(s[i]);
        }
        
        else{ 
            string str = st.top(); 
  
            if(str.compare(s[i]) == 0){ 
                st.pop(); 
            }
  
            else{
                st.push(s[i]);
            }
        } 
    } 
  
    return st.size(); 
} 
  
int main(){ 
    vector<string> s = {"ab", "aa", "aa", "bcd", "ab"};
    
    cout << removeConsSame(s); 
    
    return 0; 
}

Java Program to delete consecutive same words in a sequence

import java.util.Vector; 
import java.util.Stack; 
  
class removeSame{ 
    
    static int removeConsSame(Vector <String > s){ 
        Stack<String> st = new Stack<>(); 
       
        for(int i=0; i<s.size(); i++){ 
            if(st.empty()){ 
                st.push(s.get(i));
            }
            
            else{ 
                String str = st.peek(); 
       
                if(str.equals(s.get(i))){     
                    st.pop(); 
                }
       
                else{
                    st.push(s.get(i));
                }
            } 
        } 
        return st.size(); 
    } 
      
    public static void main(String[] args){ 
        Vector<String> s = new Vector<>(); 
  
        s.addElement("ab"); 
        s.addElement("aa"); 
        s.addElement("aa");
        s.addElement("bcd");
        s.addElement("ab");
  
        System.out.println(removeConsSame(s)); 
    } 
}

Complexity Analysis

Time Complexity

O(n) where n is the number of strings in the list. As we have just traversed over the strings, the time complexity is simply O(n), which makes the algorithm to run in linear time. But one thing to note is that strings are being compared and we have considered that strings have some constant length which is less than N. Because the string comparison in worst-case takes O(length) time.

Space Complexity

O(n) because we used space to store n strings.n Whenever the string at current index and the string at the top of stack is not same. We push the string at current index into stack. In the worst-case, we might end up pushing all the strings into the stack. This scenario results in O(n) space complexity.

Without Using Stack

Algorithm

Initialize a list of n strings.
Traverse from 0 to size of the list – 2.
1. Compare the word at the current index in the list with the word at current index+1 in the list.
  1. If both strings are different.
    1. Increment the current index
  2. Else if both the strings are same.
    1. Remove/erase both the strings from the list.
    2. Check if the current index is greater than 0
      1. Decrement the current index.
    3. Update the size of the list as size of the list – 2.
Return the size of the list.

Code

C++ Program to delete consecutive same words in a sequence

#include<bits/stdc++.h> 
using namespace std; 
  
int removeConsSame(vector <string > s){ 
    int n = s.size(); 
  
    for(int i=0; i<n-1; ){ 
        if(s[i].compare(s[i+1]) == 0){ 
            s.erase(s.begin()+i); 
            s.erase(s.begin()+i); 
  
            if(i > 0){ 
                i--; 
            }
  
            n = n-2; 
        } 
  
        else{
            i++;
        }
    } 
    return s.size(); 
} 
  
int main(){ 
    vector<string> s = {"ab", "aa", "aa", "bcd", "ab"};
    
    cout << removeConsSame(s); 
    
    return 0; 
}

Java Program to delete consecutive same words in a sequence

import java.util.Vector; 
  
class removeSame{ 
    
    static int removeConsSame(Vector <String > s){ 
        int n = s.size(); 
       
        for(int i=0; i<n-1; ){ 
            if(s.get(i).equals(s.get(i+1))){ 
                s.remove(i); 
                s.remove(i); 
       
                if(i > 0){ 
                    i--; 
                }
       
                n = n-2; 
            } 
       
            else{
                i++;
            }
        } 
        return s.size(); 
    } 
      
    public static void main(String[] args){ 
        Vector<String> s = new Vector<>(); 
  
        s.addElement("ab"); 
        s.addElement("aa"); 
        s.addElement("aa");
        s.addElement("bcd");
        s.addElement("ab");
  
        System.out.println(removeConsSame(s)); 
    } 
}

Complexity Analysis

Time Complexity

O(n^2) where n is the number of strings in the list. Since we are removing strings from the vector. Removal of any element from vector takesd linear time. Because this operation can be performed N times. The time complexity is polynomial.

Space Complexity

O(1) because we have not used any intermediate data structure to store information. The only space was required for storing strings, which is part of the input and will not be considered in calculating space complexity for the algorithm. But the program as a whole still takes O(N) space.