Problem Statement: Given a String remove all the duplicate characters from the given String.
Examples:
Example 1: Input: s = "bcabc" Output: “bca" Explanation: Duplicate Characters are removed Example 2: Input: s = "cbacdcbc" Output: "cbad" Explanation: Duplicate Characters are removed
Solution:
Disclaimer: Don’t jump directly to the solution, try it out yourself first.
Solution 1: Brute Force
Keep two pointers I, j.
i – > For traverse through the string
j – > to check if the character is already present on the left side of the string.
Traverse through the string and for every index i check if str[i] is already present on the left side of the curr idx by looping through (j —> 0 – i -1).
if the same character is found, break through the loop. Now if(i == j) which means we haven’t found the same character add it to the res string. At any point, if the same character is found then i and j will not be the same.
Code:
C++ Code
#include<bits/stdc++.h>
using namespace std;
string removeDuplicateLetters(string s) {
string ans = "";
for (int i = 0; i < s.length(); i++) {
int j = 0;
for (j = 0; j < i; j++) {
if (s[i] == s[j]) //same character found
{
break;
}
}
if (i == j) {
ans += s[i];
}
}
return ans;
}
int main() {
string str = "cbacdcbc";
cout<<"Original String: "<<str<<endl;
cout <<"After removing duplicates: " <<removeDuplicateLetters(str) << endl;
return 0;
}
Output:
Original String: cbacdcbc
After removing duplicates: cbad
Time Complexity: O(N^2)
Space Complexity: O(1)
Java Code
import java.util.*;
class Main {
public static String removeDuplicateLetters(String s) {
String ans = "";
for (int i = 0; i < s.length(); i++) {
int j = 0;
for (j = 0; j < i; j++) {
if (s.charAt(i) == s.charAt(j)) //same character found
{
break;
}
}
if (i == j) {
ans += s.charAt(i);
}
}
return ans;
}
public static void main(String[] args) {
String str = "cbacdcbc";
System.out.println("Original String: "+str);
System.out.println("After removing duplicates: "+removeDuplicateLetters(str));
}
}
Output:
Original String: cbacdcbc
After removing duplicates: cbad
Time Complexity: O(N^2)
Space Complexity: O(1)
Solution 2: Using a boolean array
The input string will only contain lowercase alphabets. So let’s create a boolean array of size 26 initialized to false.
Consider the index as the ASCII value of the character.
For example: for character ch = ‘c’. The index value will be 2.this can be achieved by doing s[i] – ‘a’ => 99 – 97 = 2 (Since ascii value of ‘c’ = 99 and ‘a’ = 97).
Keep a pointer i at the starting of the string. check if the character is already visited or not. if(s[i] – ‘a’) is false then add that character to ans and make it true.
Repeat it till we reach the end of the string.
Dry Run:
For the dry run let’s consider the size of the boolean map to be 5.
Code:
C++ Code
#include<bits/stdc++.h>
using namespace std;
string removeDuplicateLetters(string s) {
string ans = "";
vector < bool > map(26, false);
for (int i = 0; i < s.length(); i++) {
if (map[s[i] - 'a'] == false) {
ans += s[i];
map[s[i] - 'a'] = true;
}
}
return ans;
}
int main() {
string str = "cbacdcbc";
cout << "Original String: "<<str<<endl<<"After removing duplicates: "
<<removeDuplicateLetters(str) << endl;
return 0;
}
Output:
Original String: cbacdcbc
After removing duplicates: cbad
Time Complexity: O(N)
Space Complexity: O(1)
Java Code
import java.util.*;
class Main {
public static String removeDuplicateLetters(String s) {
String ans = "";
boolean[] map = new boolean[26];
for (int i = 0; i < s.length(); i++) {
if (map[s.charAt(i) - 'a'] == false) {
ans += s.charAt(i);
map[s.charAt(i) - 'a'] = true;
}
}
return ans;
}
public static void main(String[] args) {
String str = "cbacdcbc";
System.out.println("Original String: "+str+"\nAfter removing duplicates:
"+removeDuplicateLetters(str));
}
}
Output:
Original String: cbacdcbc
After removing duplicates: cbad
Time Complexity: O(N)
Space Complexity: O(1)
Special thanks to P.C.Bhuvaneshwari for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article