Identify duplicate characters in a String and replace them

Question

Found a JavaScript assignment on Codewars.com:

The goal of this exercise is to convert a string to a new string where each character in the new string is '(' if that character appears only once in the original string, or ')' if that character appears more than once in the original string. Ignore capitalization when determining if a character is a duplicate.

Examples:

"din" => "((("
"recede" => "()()()"
"Success" => ")())())"
"(( @" => "))(("

I did the assignment in Java, and came up with below code. I want to know is this the write way to code or is there a better way? If so please let me know.

private static String duplicateEncode(String word) {
 String encodeString = "";
 String decodedString = word.toLowerCase();
 for (int i = 0; i < decodedString.length(); i++) {
 if (decodedString.substring(i + 1, decodedString.length())
 .contains(String.valueOf(decodedString.charAt(i)))
 || decodedString.substring(0, i).contains(String.valueOf(decodedString.charAt(i)))) {
 encodeString += ")";
 } else {
 encodeString += "(";
 }
 }
 return encodeString;
}

Answer 1

First of all, nullbyte is exactly right about the use of a StringBuilder: using a += b for Strings roughly equals new StringBuilder().append(a).append(b).toString() under the hood and thus is a quite expensive operation.

Then, your method to check whether a given charcter exists in the string after a given index is s.substring(i).contains(ch) which again creates a superfluos string object via the substring-call. Instead, simply use s.indexOf(ch, i) to find the next index of ch after the given starting index (returns -1 for "not found").

Additionally, you might consider nullbyte's suggestion to hold the seen-or-not-seen status in a set, which also was my first intuition when reading the exercise. (Right now, you have runtime complexity of O(n^2) which you could reduce to O(n)). You only have to somehow come up with a method to revisit the first character, maybe by not using a set but by usign a map from character to number of occurrences or something like that.

Naming: why decodedString? This is not decoded in any way, this is just lowercase word. I can live with encodeString (or probably better encoded), but decodedString does not look right and does not give the reader any clue about the variable's contents.

Answer 2

public static String encode(String input) {
 input= input.toLowerCase(); //ignoring case
 StringBuilder myNewString = new StringBuilder(); // for holding new String
 for(char ch : input.toCharArray()) {
 if(StringUtils.countMatches(input, ch) > 1){ // more than 1 condition
 myNewString.append(")");
 }else{ // not repeating chars
 myNewString.append("(");
 }
 }
 myNewString.toString();
}

I am using StringUtils class from Apache Commons project. So need add this to your import: import org.apache.commons.lang3.StringUtils;

• mtj: Same as I already commented at nullbyte's answer. This is not a review. BTW, what is StringUtils?
• Sunilkumar V: oh forgot to mention, StringUtils is an Apache Commons project. Edited my original post and added package. Thanks
• nullbyte: This seems to be a little bit more concise solution than the original one. What's the time complexity of the StringUtils.countMatches() method? It's definitely O(n) which doesn't make it any better. You used a StringBuilder though.

Answer 3

Here's a better solution using a hash map:

 public static String encode(String input) {
 final StringBuilder builder = new StringBuilder();
 final Map<Character, Integer> indexMap = new HashMap<>();
 for (int index = 0; index < input.length(); index++) {
 char ch = Character.toLowerCase(input.charAt(index));
 if(indexMap.containsKey(ch)) {
 int previous = indexMap.get(ch);
 builder.replace(previous, previous+1, ")");
 builder.append(')');
 }else {
 indexMap.put(ch, index);
 builder.append('(');
 }
 }
 return builder.toString();
}

It requires O(n) time and O(n) additional space, but it's way faster than yours. Also, try using a StringBuilder if you append strings in a loop.

• Sunilkumar V: The above code will fail if the first character is coming twice. For eg: if my string is abca, i am expecting an output )((). But the above code will print ((().
• mtj: Not worth my karma to downvote this, but I don't consider "I can do it better, here's some code" a review.
• nullbyte: @mtj Well, I think it's not worth pointing out, but the OP's question is: I want to know if is this the right way to code or if there is a better way? Is this how you read it? First of all, it was not my intention to hurt someone else's feelings by "showing off" with a better solution. Secondly, there's really nothing to review, and I think I've pointed (as well as you have) the main points in my post. I could have done it more explicitly though.
• nullbyte: @SKV Ha! that's a good catch. Thanks. Please see my updated answer