Delete consecutive same words in a sequence

Given an array of n strings arr[]. The task is to determine the number of words remaining after pairwise destruction.
If two consecutive words in the array are identical, they cancel each other out. This process continues until no more eliminations are possible.

Examples: 

Input: arr[] = ["gfg", "for", "geeks", "geeks", "for"]
Output: 1
Explanation: After the first iteration, we'll have: [gfg, for, for]. Then after the second iteration, we'll have: [gfg]. No more eliminations are possible. Hence, the result is 1.

Input: arr[] = ["ab", "aa", "aa", "bcd", "ab"]
Output: 3
Explanation: After the first iteration, we'll have: [ab, bcd, ab]. We can't further destroy more strings and hence we stop and the result is 3.

Input: arr[] = ["tom", "jerry", "jerry", "tom"]
Output: 0
Explanation: After the first iteration, we'll have: [tom, tom]. After the second iteration: 'empty-array' . Hence, the result is 0.

Using Inbuilt Remove Function - O(n^2) Time

The idea is to iteratively remove consecutive same words from the array until no adjacent duplicates remain. The thought process follows a linear scan, checking adjacent elements, and if found equal, they are removed. After removal, the pointer moves back one step to recheck the new adjacency, ensuring all duplicates are handled efficiently.

// C++ program to delete consecutive  // same words from an array using  // Brute Force Method #include <bits/stdc++.h> using namespace std; // Function to remove consecutive same words int removeConsecutiveSame(vector<string>& arr) {    // Traverse the array from start  int i = 0;    while (i < arr.size() - 1) {    // If two consecutive words are the same  if (arr[i] == arr[i + 1]) {    // Remove both from vector  arr.erase(arr.begin() + i);  arr.erase(arr.begin() + i);    // Move back one step to recheck  if (i > 0) {  i--;  }  } else {    // Move to the next element  i++;  }  }    // Return the remaining number of words  return arr.size(); } // Driver code int main() {    vector<string> arr = {"gfg", "for", "geeks",   "geeks", "for"};  cout << removeConsecutiveSame(arr) << endl;  return 0; } 

// Java program to delete consecutive  // same words from an array using  // Brute Force Method import java.util.*; class GfG {    // Function to remove consecutive same words  static int removeConsecutiveSame(String[] arr) {    // Convert array to list for easier manipulation  List<String> list = new ArrayList<>(Arrays.asList(arr));  int i = 0;    while (i < list.size() - 1) {    // If two consecutive words are the same  if (list.get(i).equals(list.get(i + 1))) {    // Remove both from list  list.remove(i);  list.remove(i);    // Move back one step to recheck  if (i > 0) {  i--;  }  } else {    // Move to the next element  i++;  }  }    // Return the remaining number of words  return list.size();  }  // Driver code  public static void main(String[] args) {    String[] arr = {"gfg", "for", "geeks",   "geeks", "for"};  System.out.println(removeConsecutiveSame(arr));  } } 

# Python program to delete consecutive  # same words from an array using  # Brute Force Method # Function to remove consecutive same words def removeConsecutiveSame(arr): # Convert list for easier manipulation i = 0 while i < len(arr) - 1: # If two consecutive words are the same if arr[i] == arr[i + 1]: # Remove both from list del arr[i] del arr[i] # Move back one step to recheck if i > 0: i -= 1 else: # Move to the next element i += 1 # Return the remaining number of words return len(arr) # Driver code if __name__ == "__main__": arr = ["gfg", "for", "geeks", "geeks", "for"] print(removeConsecutiveSame(arr)) 

// C# program to delete consecutive  // same words from an array using  // Brute Force Method using System; using System.Collections.Generic; class GfG {    // Function to remove consecutive same words  static int removeConsecutiveSame(string[] arr) {    // Convert array to list for easier manipulation  List<string> list = new List<string>(arr);  int i = 0;    while (i < list.Count - 1) {    // If two consecutive words are the same  if (list[i] == list[i + 1]) {    // Remove both from list  list.RemoveAt(i);  list.RemoveAt(i);    // Move back one step to recheck  if (i > 0) {  i--;  }  } else {    // Move to the next element  i++;  }  }    // Return the remaining number of words  return list.Count;  }  // Driver code  public static void Main() {    string[] arr = {"gfg", "for", "geeks",   "geeks", "for"};  Console.WriteLine(removeConsecutiveSame(arr));  } } 

// JavaScript program to delete consecutive  // same words from an array using  // Brute Force Method // Function to remove consecutive same words function removeConsecutiveSame(arr) {    // Convert array to list for easier manipulation  let i = 0;    while (i < arr.length - 1) {    // If two consecutive words are the same  if (arr[i] === arr[i + 1]) {    // Remove both from array  arr.splice(i, 2);    // Move back one step to recheck  if (i > 0) {  i--;  }  } else {    // Move to the next element  i++;  }  }    // Return the remaining number of words  return arr.length; } // Driver code let arr = ["gfg", "for", "geeks",   "geeks", "for"]; console.log(removeConsecutiveSame(arr)); 

1 

Using Stack - O(n) Time and O(n) Space

The idea is to use a stack to efficiently remove consecutive duplicate words while maintaining order. As we iterate through the array, we check if the top element of the stack matches the current word. If they are the same, we pop the stack, otherwise, we push the word.

// C++ program to delete consecutive  // same words using Stack #include <bits/stdc++.h> using namespace std; // Function to remove consecutive same  // words using stack int removeConsecutiveSame(vector<string>& arr) {    stack<string> stk;  // Traverse the array  for (string &word : arr) {    // If stack is not empty and top element   // is same as current  if (!stk.empty() && stk.top() == word) {  stk.pop();   } else {    // Push if no consecutive duplicate  stk.push(word);   }  }    return stk.size(); } // Driver code int main() {    vector<string> arr = {"gfg", "for", "geeks",   "geeks", "for"};  cout << removeConsecutiveSame(arr) << endl;  return 0; } 

// Java program to delete consecutive  // same words using Stack import java.util.Stack; class GfG {    // Function to remove consecutive same   // words using stack  static int removeConsecutiveSame(String[] arr) {    Stack<String> stk = new Stack<>();  // Traverse the array  for (String word : arr) {    // If stack is not empty and top element   // is same as current  if (!stk.isEmpty() && stk.peek().equals(word)) {  stk.pop();  } else {    // Push if no consecutive duplicate  stk.push(word);  }  }    return stk.size();  }  // Driver code  public static void main(String[] args) {    String[] arr = {"gfg", "for", "geeks",   "geeks", "for"};  System.out.println(removeConsecutiveSame(arr));  } } 

# Python program to delete consecutive  # same words using Stack def removeConsecutiveSame(arr): stk = [] # Traverse the array for word in arr: # If stack is not empty and top element  # is same as current if stk and stk[-1] == word: stk.pop() else: # Push if no consecutive duplicate stk.append(word) return len(stk) # Driver code if __name__ == "__main__": arr = ["gfg", "for", "geeks", "geeks", "for"] print(removeConsecutiveSame(arr)) 

// C# program to delete consecutive  // same words using Stack using System; using System.Collections.Generic; class GfG {  // Function to remove consecutive same   // words using stack  static int removeConsecutiveSame(string[] arr) {    Stack<string> stk = new Stack<string>();  // Traverse the array  foreach (string word in arr) {    // If stack is not empty and top element   // is same as current  if (stk.Count > 0 && stk.Peek() == word) {  stk.Pop();  } else {    // Push if no consecutive duplicate  stk.Push(word);  }  }    return stk.Count;  }  // Driver code  static void Main() {    string[] arr = {"gfg", "for", "geeks",   "geeks", "for"};  Console.WriteLine(removeConsecutiveSame(arr));  } } 

// JavaScript program to delete consecutive  // same words using Stack function removeConsecutiveSame(arr) {    let stk = [];  // Traverse the array  for (let word of arr) {    // If stack is not empty and top element   // is same as current  if (stk.length > 0 && stk[stk.length - 1] === word) {  stk.pop();  } else {    // Push if no consecutive duplicate  stk.push(word);  }  }    return stk.length; } // Driver code let arr = ["gfg", "for", "geeks",   "geeks", "for"]; console.log(removeConsecutiveSame(arr)); 

1