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;

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.