How to Remove Duplicate Values in a String Array Github
Given a string S, remove all the consecutive duplicates. Note that this problem is different from Recursively remove all adjacent duplicates. Here we keep one character and remove all subsequent same characters.
Examples:
Attention reader! Don't stop learning now. Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer Complete Interview Preparation Course .
In case you wish to attend live classes with experts, please refer DSA Live Classes for Working Professionals and Competitive Programming Live for Students.
Input : aaaaabbbbbb Output : ab Input : geeksforgeeks Output : geksforgeks Input : aabccba Output : abcba
Recursive Solution:
The above problem can be solved using recursion.
- If the string is empty, return.
- Else compare the adjacent characters of the string. If they are same then shift the characters one by one to the left. Call recursion on string S
- If they not same then call recursion from S+1 string.
The recursion tree for the string S = aabcca is shown below.
aabcca S = aabcca / abcca S = abcca / bcca S = abcca / cca S = abcca / ca S = abca / a S = abca (Output String) / empty string
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
void removeDuplicates( char * S)
{
if (S[0] == '\0' )
return ;
if (S[0] == S[1]) {
int i = 0;
while (S[i] != '\0' ) {
S[i] = S[i + 1];
i++;
}
removeDuplicates(S);
}
removeDuplicates(S + 1);
}
int main()
{
char S1[] = "geeksforgeeks" ;
removeDuplicates(S1);
cout << S1 << endl;
char S2[] = "aabcca" ;
removeDuplicates(S2);
cout << S2 << endl;
return 0;
}
Java
import java.io.*;
class GFG {
public static String removeConsecutiveDuplicates(String input) {
if (input.length()<= 1 )
return input;
if (input.charAt( 0 )==input.charAt( 1 ))
return removeConsecutiveDuplicates(input.substring( 1 ));
else
return input.charAt( 0 ) + removeConsecutiveDuplicates(input.substring( 1 ));
}
public static void main(String[] args)
{
String S1 = "geeksforgeeks" ;
System.out.println(removeConsecutiveDuplicates(S1));
String S2 = "aabcca" ;
System.out.println(removeConsecutiveDuplicates(S2));
}
}
Python3
def removeConsecutiveDuplicates(s):
if len (s)< 2 :
return s
if s[ 0 ]! = s[ 1 ]:
return s[ 0 ] + removeConsecutiveDuplicates(s[ 1 :])
return removeConsecutiveDuplicates(s[ 1 :])
s1 = 'geeksforgeeks'
print (removeConsecutiveDuplicates(s1))
s2 = 'aabcca'
print (removeConsecutiveDuplicates(s2))
C#
using System;
class GFG {
public static string removeConsecutiveDuplicates( string input) {
if (input.Length <= 1)
return input;
if (input[0] == input[1])
return removeConsecutiveDuplicates(input.Substring(1));
else
return input[0] + removeConsecutiveDuplicates(input.Substring(1));
}
public static void Main(String[] args)
{
string S1 = "geeksforgeeks" ;
Console.WriteLine(removeConsecutiveDuplicates(S1));
string S2 = "aabcca" ;
Console.Write(removeConsecutiveDuplicates(S2));
}
}
Javascript
<script>
function removeConsecutiveDuplicates(input)
{
if (input.length<=1)
return input;
if (input[0]==input[1])
return removeConsecutiveDuplicates(input.substring(1));
else
return input[0] +
removeConsecutiveDuplicates(input.substring(1));
}
let S1 = "geeksforgeeks" ;
document.write(removeConsecutiveDuplicates(S1)+ "<br>" );
let S2 = "aabcca" ;
document.write(removeConsecutiveDuplicates(S2)+ "<br>" );
</script>
The worst case time complexity of the above solution is O(n2). The worst case happens when all characters are same.
Iterative Solution :
The idea is to check if current character is equal to the next character or not . If current character is equal to the next character we'll ignore it and when it is not equal we will add it to our answer. Since, the last element will not checked we will push it at the end of the string. For eg: s="aaaaa"
when we run the loop str="" so at the end we'll add 'a' because it is the last element.
C++
#include <bits/stdc++.h>
using namespace std;
string removeDuplicates(string s){
int n = s.length();
string str= "" ;
if (n == 0)
return str;
for ( int i=0;i<n-1;i++){
if (s[i]!=s[i+1]){
str+=s[i];
}
}
str.push_back(s[n-1]);
return str;
}
int main() {
string s1 = "geeksforgeeks" ;
cout << removeDuplicates(s1) << endl;
string s2 = "aabcca" ;
cout << removeDuplicates(s2) << endl;
return 0;
}
Java
import java.util.*;
class GFG
{
static void removeDuplicates( char [] S)
{
int n = S.length;
if (n < 2 )
{
return ;
}
int j = 0 ;
for ( int i = 1 ; i < n; i++)
{
if (S[j] != S[i])
{
j++;
S[j] = S[i];
}
}
System.out.println(Arrays.copyOfRange(S, 0 , j + 1 ));
}
public static void main(String[] args)
{
char S1[] = "geeksforgeeks" .toCharArray();
removeDuplicates(S1);
char S2[] = "aabcca" .toCharArray();
removeDuplicates(S2);
}
}
Python3
def removeDuplicates(S):
n = len (S)
if (n < 2 ) :
return
j = 0
for i in range (n):
if (S[j] ! = S[i]):
j + = 1
S[j] = S[i]
j + = 1
S = S[:j]
return S
if __name__ = = '__main__' :
S1 = "geeksforgeeks"
S1 = list (S1.rstrip())
S1 = removeDuplicates(S1)
print ( * S1, sep = "")
S2 = "aabcca"
S2 = list (S2.rstrip())
S2 = removeDuplicates(S2)
print ( * S2, sep = "")
C#
using System;
class GFG
{
static void removeDuplicates( char [] S)
{
int n = S.Length;
if (n < 2)
{
return ;
}
int j = 0;
for ( int i = 1; i < n; i++)
{
if (S[j] != S[i])
{
j++;
S[j] = S[i];
}
}
char []A = new char [j+1];
Array.Copy(S,0, A, 0, j + 1);
Console.WriteLine(A);
}
public static void Main(String[] args)
{
char []S1 = "geeksforgeeks" .ToCharArray();
removeDuplicates(S1);
char []S2 = "aabcca" .ToCharArray();
removeDuplicates(S2);
}
}
Javascript
<script>
const removeDuplicates = (s) => {
let n = s.length;
let str = "" ;
if (n == 0)
return str;
for (let i = 0; i < n - 1; i++) {
if (s[i] != s[i + 1]) {
str += s[i];
}
}
str += s[n-1];
return str;
}
let s1 = "geeksforgeeks" ;
document.write(`${removeDuplicates(s1)}<br/>`)
let s2 = "aabcca" ;
document.write(removeDuplicates(s2))
</script>
Time Complexity : O(n)
Auxiliary Space : O(1)
This article is contributed by Ankur Singh. 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.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
How to Remove Duplicate Values in a String Array Github
Source: https://www.geeksforgeeks.org/remove-consecutive-duplicates-string/