Remove duplicate character from a given string

This is one of the tricky question asked in the interviews. Not only to check logical ability of candidates but to check their understanding about algorithms and complexities.

So here is the Problem statement:

 How to remove duplicate characters from String in Java? For example, if given String is "aaaaaa" then output should be "a", because rest of  the "a" are duplicates. Similarly, if the input is "abcd" then output should also be "abcd"  because there is no duplicate character in this String.

Algorithm:

 This algorithm goes through each character of String to check if its a duplicate of already found character. It skip the duplicate character by inserting 0, which is later used to filter those characters and update the non-duplicate character. 

Time Complexity of this solution is O(n^2), excluded to UniqueString() method, which creates String from character array. 

This method will work even if String contains more than one duplicate character.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86

/** * * Java Program to remove duplicate characters from String. * * @author Ram.Dutt */ public class RemoveDuplicateChar { public static void main(String args[]) { String[] testdata = { "aabaaaaascs", "abcd", "aaaa", null, "", "aaabbb", "abababa" }; for (String input : testdata) { System.out.printf("Input : %s Output: %s %n", input, removeDuplicates(input)); } System.out.println("Calling removeDuplicatesFromString(String str)."); for (String input : testdata) { System.out.printf("Input : %s Output: %s %n", input, removeDuplicatesFromString(input)); } } public static String removeDuplicates(String word) { if (word == null || word.length() < 2) { return word; } int pos = 1; // possible position of duplicate character char[] characters = word.toCharArray(); for (int i = 1; i < word.length(); i++) { int j; for (j = 0; j < pos; ++j) { if (characters[i] == characters[j]) { break; } } if (j == pos) { characters[pos] = characters[i]; ++pos; } else { characters[pos] = 0; ++pos; } } return toUniqueString(characters); } /* * * This solution assumes that given input String only contains * ASCII * characters. You should ask this question to your Interviewer, * if he * says ASCII then this solution is Ok. This Algorithm * uses additional * memory of constant size. */ public static String removeDuplicatesFromString(String input) { if (input == null || input.length() < 2) { return input; } boolean[] ASCII = new boolean[256]; char[] characters = input.toCharArray(); ASCII[input.charAt(0)] = true; int dupIndex = 1; for (int i = 1; i < input.length(); i++) { if (!ASCII[input.charAt(i)]) { characters[dupIndex] = characters[i]; ++dupIndex; ASCII[characters[i]] = true; } else { characters[dupIndex] = 0; ++dupIndex; } } return toUniqueString(characters); } /* * * Utility method to convert Character array to String, omitting * NUL * character, ASCII value 0. */ public static String toUniqueString(char[] letters) { StringBuilder sb = new StringBuilder(letters.length); for (char c : letters) { if (c != 0) { sb.append(c); } } return sb.toString(); } }

That is it. You can use different logic too to remove duplicate values from the array in Java as well.

Happy reading!