Accenture Interview Question
Software EngineersCountry: India
import java.util.*;
import java.io.*;
public class RemoveDuplicatesFromString {
public static void main(String args[]) throws IOException
{
Scanner sc=new Scanner(System.in);
String str=sc.next();
String s="";
for(int i=0;i<str.length();i++)
{
boolean present=false;
char ch=str.charAt(i);
for(int j=1;j<str.length();j++)
{
if(str.charAt(j)==ch && j!=i)
{present=true;break;}
}
if (present==false)
{s=s+str.charAt(i);}
}
System.out.println("Output string is : "+s);
}
}
A simple hashmap will do the trick.
public class RemoveDupesFromString
{
HashMap<Character, List<Integer>> characters = null;
public String removeDupes(String input)
{
//Error and edges
if(input == null || input.isEmpty()) {throw new IllegalArgumentException();}
if(input.length() == 1) { return input;}
characters = new HashMap<>();
int index = 0;
List<Integer> indeces = new ArrayList<>();
for(char current : input.toCharArray())
{
if(characters.containsKey(current))
indeces = characters.get(current);
else
indeces = new ArrayList<>();
indeces.add(index);
characters.put(current, indeces); //first occurrence
index++;
indeces = new ArrayList<>();
}
for(Entry<Character, List<Integer>> entry : characters.entrySet())
{
if(entry.getValue().size() > 1)
{
input = input.replace(entry.getKey().toString(), "");
}
}
return input;
}
}
The following code will remove all characters appearing twice or even times, but will preserve those occuring thrice.
/* Remove duplicates from string given " cutcopypaste " Return "uoyase"*/
#include <stdio.h>
void remove_dup(char * s)
{
char * a = s;
printf("\n s= %s", s);
printf("\n a=%s", a);
short r[256];
int i = 0;
while (a[i] != '\0')
{
if (r[a[i]] == 0)
r[a[i]] = 1;
else
r[a[i]] = 0;
i++;
}
char b[200];
int j = 0;
i = 0;
while (a[i] != '\0')
{
if (r[a[i]] == 0)
b[j++] = a[i];
i++;
}
b[j++] = '\0';
printf("\n %s", b);
return;
}
int main()
{
int i;
remove_dup("Remove all the duplicate characters");
scanf_s("%d", &i);
return 0;
}
/* Remove duplicates from string given " cutcopypaste " Return "uoyase"
This one removes all duplicates, so aaa will be removed and will not return a*/
#include <stdio.h>
void remove_dup(char * s)
{
char * a = s;
printf("\n s= %s", s);
printf("\n a=%s", a);
short r[256];
int i;
for (i = 0; i < 256; i++)
r[i] = 0;
i = 0;
while (a[i] != '\0')
{
r[a[i]]++;
printf("\n a[%c] is getting visited ", a[i]);
i++;
}
char b[200];
int j = 0;
i = 0;
while (a[i] != '\0')
{
if (r[a[i]] < 2)
b[j++] = a[i];
i++;
}
b[j++] = '\0';
printf("\n String is %s", b);
return;
}
int main()
{
int i;
remove_dup("abcdddddefgabc");
scanf_s("%d", &i);
return 0;
}
c#.
O(n) time.
O(1) space.
private static string RemoveDuplicatesFromString( string str ) {
int[] arr = new int[256];
for ( int i = 0; i < str.Length; i++ ) {
arr[ str[ i ] ]++;
}
StringBuilder sb = new StringBuilder();
for ( int i = 0; i < str.Length; i++ ) {
sb.Append( arr[ str[ i ] ] == 1 ? str[ i ].ToString() : "" );
}
return sb.ToString();
}
1- fill a hashtable with counts of each characters
2- iterate through the string again and add only the characters with count 1 to the string.
Space O(n) for the hashtable
Time O(n) for iterating through string twice
public static string RemoveDuplicate(string str)
{
Dictionary<char, int> dict = new Dictionary<char, int>();
for (int i = 0; i < str.Length; i++)
{
if (dict.ContainsKey(str[i]))
{
dict[str[i]]++;
}
else
{
dict.Add(str[i], 1);
}
}
string str2 = "";
for (int i = 0; i < str.Length; i++)
{
if (dict[str[i]] == 1)
str2 += str[i];
}
return str2;
}
Code in Java
Time : O(n)
Space : O(n)
private static void removeDuplicates(String input){
char[] chars=input.toCharArray();
int[] alphabetCount=new int[26];//It will keep count of every appeared alphabet in given string
for(Character c : chars){
alphabetCount[c-97]++;
}
String output="";
for(Character c : chars){
if(alphabetCount[c-97]==1){
output+=c;
}
}
System.out.println("Output string is --> "+output);
}
#include <stdio.h>
int main()
{
char string_name[] ="cutcopypaste";
char *read1,*read2,*write;
char array[255] = {0};
int count = 0;
int index;
read1 = string_name;
read2 = string_name;
write = string_name;
while(*read1!= '\0')
{
index = (int) *read1; //eqv ascii value
array[index] = array[index]+1;
read1++;
}
index = 0;
while(*read2!='\0')
{
index = (int) *read2;//eqv ascii value
if((array[index] == 1))
{
*write++ = *read2;
}
read2++;
}
*write = '\0';
printf("%s",string_name);
return 0;
}
#include <stdio.h>
int main()
{
char string_name[] ="cutcopypaste";
char *read1,*read2,*write;
char array[255] = {0};
int count = 0;
int index;
read1 = string_name;
read2 = string_name;
write = string_name;
while(*read1!= '\0')
{
index = (int) *read1; //eqv ascii value
array[index] = array[index]+1;
read1++;
}
index = 0;
while(*read2!='\0')
{
index = (int) *read2;//eqv ascii value
if((array[index] == 1))
{
*write++ = *read2;
}
read2++;
}
*write = '\0';
printf("%s",string_name);
return 0;
}
Algorithm to solve:
- Ashwin February 05, 20161. Create a 26 flag array.
2. If visited mark the last visited position in the flag array.
3. If already visited, make that index of the string as ' '.
4. Remove all spaces in the string