6
\$\begingroup\$

Implementation for a relatively basic programming challenge:

Find the first unique character in a string

So evaluating the string ABCA would return B.

My implementation does the following:

  • Initialize a boolean array that is the size of the input string - note that the default initialization value is false
  • The boolean array's values correspond to whether or not the input string character that shares the same index value is unique or not.
  • Compare each character in the input string against all the characters to the right of it
  • If there is a match, set the values in the boolean array to true for each character index value.
  • Iterate through the boolean array and return the first value that is false.
  • If iteration completes, throw a NoUniqueCharacters Exception

Is there a better approach?

  • I briefly considered using some sort of Ordered Map (if such a thing exists) that maps characters to their counts where the character key values are ordered by their index in the string
public Character identifyFirstUniqueCharacterInString(final String string) throws NoUniqueCharactersException {
        final char[] chars = string.toCharArray();
        final boolean[] repeatedCharacterIndices = new boolean[chars.length];
        for (int candidateCharacterIndex = 0; candidateCharacterIndex < chars.length; candidateCharacterIndex++) {
            for (int comparisonCharacterIndex = candidateCharacterIndex + 1; comparisonCharacterIndex < chars.length; comparisonCharacterIndex++) {
                if (chars[candidateCharacterIndex] == chars[comparisonCharacterIndex]) {
                    repeatedCharacterIndices[candidateCharacterIndex] = true;
                    repeatedCharacterIndices[comparisonCharacterIndex] = true;
                }
            }
        }
        for (int repeatedCharacterIndex = 0; repeatedCharacterIndex < repeatedCharacterIndices.length; repeatedCharacterIndex++) {
            if (!repeatedCharacterIndices[repeatedCharacterIndex]) {
                return chars[repeatedCharacterIndex];
            }
        }

        throw new NoUniqueCharactersException();
    }
\$\endgroup\$
  • 2
    \$\begingroup\$ Deleting your own question after you have received an answer isn't fair. I have undeleted the question. \$\endgroup\$ – 200_success Nov 30 '15 at 4:47
  • 2
    \$\begingroup\$ Apologies, I realized how trivial this question was and my reaction was to delete it. I've accepted the answer. \$\endgroup\$ – Jae Bradley Nov 30 '15 at 13:20
  • \$\begingroup\$ better to take one counter and compare every character if count increase break the loop and set counter it 0 or iterate with next character or if counter is not increase that mean its unique word. \$\endgroup\$ – Pankaj Gupta Nov 30 '15 at 16:41
  • \$\begingroup\$ @JaeBradley docs.oracle.com/javase/7/docs/api/java/util/LinkedHashMap.html -> Ordered Map that keep the insertion order, might be useful if you want to try the Ordered map way. \$\endgroup\$ – Marc-Andre Nov 30 '15 at 17:43
  • \$\begingroup\$ @JaeBradley Please unaccept my answer as my answer is unsuitable. \$\endgroup\$ – SirPython Nov 30 '15 at 18:57
4
\$\begingroup\$

One alternative is to let String.indexOf(int, int) do the iteration for you:

return IntStream.range(0, input.length())
                .filter(i -> input.indexOf(input.charAt(i), i + 1) == -1)
                .mapToObj(i -> Character.valueOf(input.charAt(i)))
                .findFirst().orElseThrow(NoUniqueCharactersException::new);
  • Loop with IntStream from 0 (inclusive) to the length of input (exclusive).
  • Filter for indices i where input.indexOf(input.charAt(i), i + 1) gives -1, i.e. there is no occurrence of the character at index i past that position.
  • For any matches, convert to our desired Character wrapper class using mapToObj().
  • In order to return the first character, we findFirst() from the IntStream, orElseThrow() our custom NoUniqueCharactersException.

A second alternative is to use String.lastIndexOf(int):

// instead of this
// .filter(i -> input.indexOf(input.charAt(i), i + 1) == -1)
// use this
.filter(i -> i == input.lastIndexOf(input.charAt(i)))

In this case, if the last index of the character at position i is indeed i, that means we have found our unique character.

\$\endgroup\$
0
\$\begingroup\$

I find the code very hard to read because of the very long variable names. I therefore rewrote it to:

@Nullable
public static Character firstUnique(String str) {
    char[] chars = str.toCharArray();
    boolean[] repeated = new boolean[chars.length];
    for (int i = 0; i < chars.length; i++) {
        for (int j = i + 1; j < chars.length; j++) {
            if (chars[i] == chars[j]) {
                repeated[i] = true;
                repeated[j] = true;
            }
        }
    }
    for (int i = 0; i < repeated.length; i++) {
        if (!repeated[i]) {
            return chars[i];
        }
    }

    return null;
}

Now the code fits easily on the screen and looks like most other code that is doing string operations. I also removed all redundant parts from the method name:

  • identify was wrong. A character does not have an identity since Character and char are value types.
  • Character was redundant because the return type already says Character.
  • InString was redundant because the method parameter is of type String.

Regarding the algorithmic complexity: Your code works fine for short strings. But you should not run this code on strings of 16M characters since it would take \$2^{47}\$ basic operations. Therefore, if this code is ever going to work with long strings, you should have an alternative algorithm:

@Nullable
static OptionalInt firstUniqueLong(String str) {
    BitSet once = new BitSet();
    BitSet dups = new BitSet();
    str.codePoints().forEach(codePoint -> (once.get(codePoint) ? dups : once).set(codePoint));
    return str.codePoints().filter(codePoint -> !dups.get(codePoint)).findFirst();
}

This code also works for small strings.

The execution time is \$\mathcal O(\text{str.length})\$, as opposed to the \$\mathcal O(\text{str.length}^2)\$ of your code.

The space requirement of this code depends not on the length of the string but on the actual characters (well, Unicode code points) in it. For ASCII it works well, but since the current implementation for BitSet allocates a simple array, inserting a single emoji in the string allocates 2 times 16 kilobytes of memory. Characters with even higher code points might raise the memory requirement to 2 times 140 kilobytes (= Character.MAX_CODE_POINT / 8).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.