Delete consecutive same words in a sequence
Last Updated :
14 Sep, 2023
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.
Examples:
Input : ab aa aa bcd ab
Output : 3
As aa, aa destroys each other so,
ab bcd ab is the new sequence.
Input : tom jerry jerry tom
Output : 0
As first both jerry will destroy each other.
Then sequence will be tom, tom they will also destroy
each other. So, the final sequence doesn’t contain any
word.
Method 1:
1- Start traversing the sequence by storing it in vector.
a) Check if the current string is equal to next string
if yes, erase both from the vector.
b) And check the same till last.
2- Return vector size.
Implementation:
C++
#include<bits/stdc++.h>
using namespace std;
int removeConsecutiveSame(vector <string > v)
{
int n = v.size();
for (int i=0; i<n-1; )
{
if (v[i].compare(v[i+1]) == 0)
{
v.erase(v.begin()+i);
v.erase(v.begin()+i);
if (i > 0)
i--;
n = n-2;
}
else
i++;
}
return v.size();
}
int main()
{
vector<string> v = { "tom", "jerry", "jerry", "tom"};
cout << removeConsecutiveSame(v);
return 0;
}
|
Java
import java.util.Vector;
class Test
{
static int removeConsecutiveSame(Vector <String > v)
{
int n = v.size();
for (int i=0; i<n-1; )
{
if (v.get(i).equals(v.get(i+1)))
{
v.remove(i);
v.remove(i);
if (i > 0)
i--;
n = n-2;
}
else
i++;
}
return v.size();
}
public static void main(String[] args)
{
Vector<String> v = new Vector<>();
v.addElement("tom"); v.addElement("jerry");
v.addElement("jerry");v.addElement("tom");
System.out.println(removeConsecutiveSame(v));
}
}
|
Python3
def removeConsecutiveSame(v):
n = len(v)
i = 0
while(i < n - 1):
if ((i + 1) < len(v)) and (v[i] == v[i + 1]):
v = v[:i]
v = v[:i]
if (i > 0):
i -= 1
n = n - 2
else:
i += 1
return len(v[:i - 1])
if __name__ == '__main__':
v = ["tom", "jerry", "jerry", "tom"]
print(removeConsecutiveSame(v))
|
C#
using System;
using System.Collections.Generic;
class GFG
{
public static int removeConsecutiveSame(List<string> v)
{
int n = v.Count;
for (int i = 0; i < n - 1;)
{
if (v[i].Equals(v[i + 1]))
{
v.RemoveAt(i);
v.RemoveAt(i);
if (i > 0)
{
i--;
}
n = n - 2;
}
else
{
i++;
}
}
return v.Count;
}
public static void Main(string[] args)
{
List<string> v = new List<string>();
v.Add("tom");
v.Add("jerry");
v.Add("jerry");
v.Add("tom");
Console.WriteLine(removeConsecutiveSame(v));
}
}
|
Javascript
<script>
function removeConsecutiveSame(v)
{
let n = v.length;
for (let i = 0; i < n - 1;)
{
if (v[i] == (v[i + 1]))
{
v.splice(i, 1);
v.splice(i, 1);
if (i > 0) {
i--;
}
n = n - 2;
}
else {
i++;
}
}
return v.length;
}
let v = [];
v.push("tom");
v.push("jerry");
v.push("jerry");
v.push("tom");
document.write(removeConsecutiveSame(v));
</script>
|
Time Complexity: O(n)
Auxiliary Space : O(1)
Method 2:(Using Stack)
1- Start traversing the strings and push into stack.
a) Check if the current string is same as the string
at the top of the stack
i) If yes, pop the string from top.
ii) Else push the current string.
2- Return stack size if the whole sequence is traversed.
Implementation:
C++
#include<bits/stdc++.h>
using namespace std;
int removeConsecutiveSame(vector <string> v)
{
stack<string> st;
for (int i=0; i<v.size(); i++)
{
if (st.empty())
st.push(v[i]);
else
{
string str = st.top();
if (str.compare(v[i]) == 0)
st.pop();
else
st.push(v[i]);
}
}
return st.size();
}
int main()
{
vector<string> V = { "ab", "aa", "aa", "bcd", "ab"};
cout << removeConsecutiveSame(V);
return 0;
}
|
Java
import java.util.Stack;
import java.util.Vector;
class Test
{
static int removeConsecutiveSame(Vector <String> v)
{
Stack<String> st = new Stack<>();
for (int i=0; i<v.size(); i++)
{
if (st.empty())
st.push(v.get(i));
else
{
String str = st.peek();
if (str.equals(v.get(i)))
st.pop();
else
st.push(v.get(i));
}
}
return st.size();
}
public static void main(String[] args)
{
Vector<String> v = new Vector<>();
v.addElement("ab"); v.addElement("aa");
v.addElement("aa");v.addElement("bcd");
v.addElement("ab");
System.out.println(removeConsecutiveSame(v));
}
}
|
Python3
def removeConsecutiveSame(v):
st = []
for i in range(len(v)):
if (len(st) == 0):
st.append(v[i])
else:
Str = st[-1]
if (Str == v[i]):
st.pop()
else:
st.append(v[i])
return len(st)
if __name__ == '__main__':
V = [ "ab", "aa", "aa", "bcd", "ab"]
print(removeConsecutiveSame(V))
|
C#
using System;
using System.Collections.Generic;
class GFG
{
public static int removeConsecutiveSame(List<string> v)
{
Stack<string> st = new Stack<string>();
for (int i = 0; i < v.Count; i++)
{
if (st.Count == 0)
{
st.Push(v[i]);
}
else
{
string str = st.Peek();
if (str.Equals(v[i]))
{
st.Pop();
}
else
{
st.Push(v[i]);
}
}
}
return st.Count;
}
public static void Main(string[] args)
{
List<string> v = new List<string>();
v.Add("ab");
v.Add("aa");
v.Add("aa");
v.Add("bcd");
v.Add("ab");
Console.WriteLine(removeConsecutiveSame(v));
}
}
|
Javascript
<script>
function removeConsecutiveSame(v)
{
let st = [];
for (let i = 0; i < v.length; i++)
{
if (st.length == 0)
{
st.push(v[i]);
}
else
{
let str = st[st.length - 1];
if (str == v[i])
{
st.pop();
}
else
{
st.push(v[i]);
}
}
}
return st.length;
}
let v = [];
v.push("ab");
v.push("aa");
v.push("aa");
v.push("bcd");
v.push("ab");
document.write(removeConsecutiveSame(v));
</script>
|
Time Complexity: O(N), where N is the size of the given sequence.
Auxiliary Space: O(N), since we are using a stack to store the elements of the sequence.
Please Login to comment...