CareerCup

/* Function removes duplicate characters from the string
   This function work in-place and fills null characters
   in the extra space left */
char *removeDups(char *str)
{
  bool bin_hash[NO_OF_CHARS] = {0};
  int ip_ind = 0, res_ind = 0; 
  char temp;    
 
  /* In place removal of duplicate characters*/ 
  while(*(str + ip_ind))
  {
    temp = *(str + ip_ind);
    if(bin_hash[temp] == 0)
    {
        bin_hash[temp] = 1;
        *(str + res_ind) = *(str + ip_ind);
        res_ind++;         
    }
    ip_ind++;
  }      
 
  /* After above step string is stringiittg.
     Removing extra iittg after string*/       
  *(str+res_ind) = '\0';   
   
  return str;
}

sort a string
compare character to its next, if match, then dup found, if next character is EoS terminate.

qsort(buffer, size);
for(int i =0; i< size-1; i ++)
{
	if( buffer[i+1] == '\0' )
		break;
	if( buffer[i] == buffer[i+1] )
		break;
}
return i;

Without sorting I am not sure how can we detect or remove duplicates

Use HeapSort to sort the char array. HeapSort can be done in-place. Once the array is sorted, remove duplicates.

1) Sort the elements.
2) Now in a loop, remove duplicates by comparing the current character with previous character.
3) Remove extra characters at the end of the resultant string.
Time Complexity: O(nlogn) and Space Complexity: O(1)

below is solution for array of integer but should work for all types of data

1.) bruteforce - going thru the array and marking duplicates
2.) use an hashset to put data and it should remove duplicates
3.) sort and then compare with previous

public class RemoveDuplicates {
	
	/**
	 * brute force- o(N square)
	 * 
	 * @param input
	 * @return
	 */
	public static int[] removeDups(int[] input){
		boolean[] isSame = new boolean[input.length];
		int sameNums = 0;
		
		for( int i = 0; i < input.length; i++ ){
			for( int j = i+1; j < input.length; j++){
				if( input[j] == input[i] ){ //compare same
					isSame[j] = true;
					sameNums++;
				}
			}
		}
		
		//compact the array into the result.
		int[] result = new int[input.length-sameNums];
		int count = 0;
		for( int i = 0; i < input.length; i++ ){
			if( isSame[i] == true) {
				continue;
			}
			else{
				result[count] = input[i];
				count++;
			}
		}
		
		return result;
	}
	
	/**
	 * set - o(N)
	 * does not guarantee order of elements returned - set property
	 * 
	 * @param input
	 * @return
	 */
	public static int[] removeDups1(int[] input){
		HashSet myset = new HashSet();
		
		for( int i = 0; i < input.length; i++ ){
			myset.add(input[i]);
		}
		
		//compact the array into the result.
		int[] result = new int[myset.size()];
		Iterator setitr = myset.iterator();
		int count = 0;
		while( setitr.hasNext() ){
			result[count] = (int) setitr.next();
			count++;
		}
		
		return result;
	}
	
	/**
	 * quicksort - o(Nlogn)
	 * 
	 * @param input
	 * @return
	 */
	public static int[] removeDups2(int[] input){
		Sort st = new Sort();
		st.quickSort(input, 0, input.length-1); //input is sorted
		
		//compact the array into the result.
		int[] intermediateResult = new int[input.length];
		int count = 0;
		int prev = Integer.MIN_VALUE;
		for( int i = 0; i < input.length; i++ ){
			if( input[i] != prev ){
				intermediateResult[count] = input[i];
				count++;
			}
			prev = input[i];
		}
		
		int[] result = new int[count];
		System.arraycopy(intermediateResult, 0, result, 0, count);
		
		return result;
	}
	
	
	public static void printArray(int[] input){
		for( int i = 0; i < input.length; i++ ){
			System.out.print(input[i] + " ");
		}
	}
	
	public static void main(String[] args){
		int[] input = {5,6,8,0,1,2,5,9,11,0};
		RemoveDuplicates.printArray(RemoveDuplicates.removeDups(input));
		System.out.println();
		RemoveDuplicates.printArray(RemoveDuplicates.removeDups1(input));
		System.out.println();
		RemoveDuplicates.printArray(RemoveDuplicates.removeDups2(input));
	}
}

package removeDuplicate;

public class removeDuplicateWithoutExtraBuffer {

public static void removeDuplicate(String str) {
for(int i=0;i<str.length();i++) {
for(int j=i+1;j<str.length();j++) {
if(str.charAt(i)==str.charAt(j)) {
str = str.substring(0, j) + str.substring(j + 1);
i--;
break;
}
}
}
System.out.println("String without any duplciate is "+str);

}
public static void main(String[] args) {
String str = "swaatiaaaawawassawawtststatsstattasasasatssatatsastasatasattttaaaasssssssss";
removeDuplicate(str);
}

}

import java.util.*;
public class RemoveDuplicate1 {
private static Scanner in;
private static char temp;
private static int last;

public static void main(String[] args) {
// TODO Auto-generated method stub
char str[] = new char[100];
System.out.println("enter string");
in = new Scanner(System.in);
str = in.nextLine().toCharArray();

int len = str.length;
last = len;
for (int i = 0; i < last-1; i++) {
for (int j = last - 1; j > i; j--) {
if (str[i] == str[j]) {
temp = str[last-1];
str[last-1]=str[j];
str[j]=temp;
last--;
}
}
}
for(int i=0;i<last;i++)
System.out.print(str[i]);
}
}

import java.util.*;
public class RemoveDuplicate {
private static Scanner in;
private static char temp;
private static int last;

public static void main(String[] args) {
char str[] = new char[100];
System.out.println("enter string");
in = new Scanner(System.in);
str = in.nextLine().toCharArray();

int len = str.length;
last = len;
for (int i = 0; i < last-1; i++) {
for (int j = last - 1; j > i; j--) {
if (str[i] == str[j]) {
temp = str[last-1];
str[last-1]=str[j];
str[j]=temp;
last--;
}
}
}
for(int i=0;i<last;i++)
System.out.print(str[i]);
}
}

public static String removeDuplicateChar(String s)
 {
	 StringBuilder sbr = new StringBuilder();
	 for(int i=0; i<s.length();i++)
	 {
		 String str = s.substring(i, i+1);
		 if(sbr.indexOf(str) == -1)
		 {
			 sbr.append(str);
		 }
	 }
	 return sbr.toString(); 
 }

void removeduplicates(string str) 
{
  int l, index;
  string res_str="";
  l = str.length();
  bool flag[26];
  fill_n(flag, 26, 0);
  for (int i=0; i<l; i++)
  {
    index = str[i] - 97;
    if (flag[index] == 0)
    {
      flag[index] = 1;
      res_str += str[i];
    }
  }
  cout<<res_str<<endl;
}

// Design an algorithm and write code to remove the duplicate characters in a string without using any additional buffer. NOTE: One or two additional variables are fine. 
	//An extra copy of the array is not.
	// Complexity  O ( n )
	public static void removeDuplicates(char str[]){
		boolean letters [] = new boolean[256];
		int index = 0 ;
		for(int i = 0; i < str.length ; i++ ){
			char current = str[i];
			
			if(!letters[current] || current == ' '){
				str[index++]  = str[i];
				letters[current]  = true;
			}
		}
		for(int i = index; i < str.length; i ++)
		{
			str[i]  = ' ';
		}
		
	}