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.
If you like GeeksforGeeks and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.
Feeling lost in the world of random DSA topics, wasting time without progress? It's time for a change! Join our DSA course, where we'll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 geeks!