Delete consecutive same words in a sequence

Last Updated on December 14, 2022 by Prepbytes

Problem statement

Given an array of strings, if two consecutive strings are the same they will destroy each other. Your task is to find the number of remaining strings from the given array which do not get destroyed.

Input: An array of strings.
Output: Integer.

Test cases:

Input: S = [“prep”, “bytes”, “bytes”, “prep”, “dsa”]
Output: 1

Explanation:

“bytes” at index 1 will get destroyed with “bytes” at index 2.
Then the array will look like [“prep”, “prep”, “dsa”].
Now “prep” at index 0 will get destroyed with “prep” at index 1.
Hence, only “dsa” will be left after all the pairwise destruction. So, the output will be 1.

Naive Approach

A simple approach can be to traverse the given array and if we found two consecutive strings, we will remove them from the array. We will continue this approach until all the strings are pairwise distinct.

Code implementation

import java.util.*;
public class Main
{
	public static void main(String[] args) {
	    String[] arr = {"prep", "bytes", "bytes", "prep", "dsa"};
	    System.out.println(remainingStringCount(arr));
	}
	Public static int remainingStringCount(String[] arr){
	    ArrayList<String> arrList = new ArrayList<>(Arrays.asList(arr));
	    boolean distinct = false;
	    do{
	        distinct = false;
	        for(int i = 0;i<arrList.size()-1;i++){
	            if(arrList.get(i)==arrList.get(i+1)){
	                distinct = true;
	                arrList.remove(i);
	                
	                // Here we are again removing string at index 'i'
	                // because after removing the string in the above line,
	                // the string at index 'i+1' will move to 'i'.
	                arrList.remove(i);
	            }
	        }
	    }while(distinct);
	    return arrList.size();
	}
}

Time complexity: O(n²), where n is the number of strings. Consider an array like [“a”, “b”, “c”, “c”, “b”, “a”]. The while loop will run three times and the inner loop will check all the remaining elements. Hence, the asymptotic time complexity in the worst case will be O(n²).

Space Complexity: O(n). We are using arraylist to store all the strings. If we can directly remove strings from the array then the space complexity will be O(1).

Approach – Using Stack

In the stack approach, we will move strings from the input array to the stack one by one. If the stack is empty or the top of the stack is not equal to the current string, we will move the current string to the stack. Otherwise, If the top of the stack is equal to the current string, then we will remove the top of the stack and check the next string.

Algorithm

1. Initialize a new stack.
2. For i in 0 to n
   a. If the stack is empty or st.top != arr[i]
   i. Push arr[i] into stack.
   b. If st.top == arr[i]
   i. Remove top of the stack
3. Return size of the stack.

Dry Run:

Code Implementation:

import java.util.*;
public class Main
{
	public static void main(String[] args) {
	    String[] arr = {"prep", "bytes", "bytes", "prep", "dsa"};
		System.out.println(remainingStringCount(arr));
	}
	public static int remainingStringCount(String[] arr){
	    // Initialize a new stack.
	    Stack<String> st = new Stack<>();
	    
	    // Traverse the string one by one.
	    for(int i = 0;i<arr.length;i++){
	        
	        // If stack is empty or the top of the stack is not equal to current string
	        // push the current string into the stack.
	        if(st.isEmpty() || st.peek() != arr[i]){
	            st.push(arr[i]);
	        }
	        
	        // Otherwise, it means the top of the stack is same is same as the current string
	        // so remove the top of the stack.
	        else {
	            st.pop();
	        }
	    }
	    
	    // Return the size of the stack.
        return st.size();
	}
}

Output:
1

Time complexity: O(n), we will push and pop each string from the stack at most once. Hence, the time complexity will be O(n).

Space Complexity: O(n). We are using a stack which can have an element if all the strings are distinct. Hence, the space complexity will be O(n).

We tried to discuss the Delete consecutive same words in a sequence. We hope this article gives you a better understanding of Delete consecutive same words in a sequence. PrepBytes also provides a good collection of Foundation Courses that can help you enhance your coding skills. Want to make sure you ace the interview in one go? Join our Placement Program which will help you get prepared and land your dream job at MNCs. Mentors of Prepbytes are highly experienced and can provide you with basic, in-depth subject knowledge for better understanding.