Amazon.com

www.amazon.com
Engaged Employer

Interview

# Write a function to remove all redundant characters in a

given string.

0

solution in Java: public class RemoveDuplicateChars { String str1 = "foo"; public String removeDuplicates(String str1) { String result = ""; for (int i=0; i < str1.length(); i++) { if (!result.contains("" + str1.charAt(i))) { result += "" + str1.charAt(i); } } return result; // returns "fo" } }

Chase on Jan 11, 2014
1

Careful, because result.contains may require n time to go through, where n is the length of the result. So the worst case would be O(n^2). You could optimise in time sorting the string in O(n logn) time and then look for adjacent elements or if space is not a problem use a Map<String, Integer>, where the key is a char of the string and the value is the number of occurrences of the char. At the end consider only chars that occurrence once. This would be O(n) in time and O(n) in space.

Luca on Jan 13, 2014
2

public static String removeDups(String str){ if(str == null) return null; boolean[] carr = new boolean[256]; String result = ""; for(int i=0;i<str.length();i++){ if(!carr[str.charAt(i)]){ carr[str.charAt(i)] = true; result+=str.charAt(i); } } return result; }

Naan on Jan 29, 2014