Find the first unique character in a string

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

2021-10-31:

Wells... as pointed out by @RiaD's comment, the original answer below failed to account for values seen. That means a simple string like aabc will return the second a, as it wrongly thinks it's unique having not appeared again.

I think where we got befuddled was trying to keep a mix of arrays in order to know what's unique and where they are. An alternative, arguably simpler way, is to use a map and then iterating on it. (so two iterations...?)

-
The first iteration collects into a Map, with a merging function that returns a -1 when we encounter repeated values.

-
The next iteration on the new map keeps only the valid positions (>= 0), sorts by the value and returns the minimum one.

public static char firstUnique(String input) {
      return IntStream.range(0, input.length()).boxed() // first iteration
              .collect(Collectors.toMap(input::charAt, i -> i, (a, b) -> -1))
              .entrySet().stream() // second iteration
              .filter(entry -> entry.getValue() >= 0)
              .min(Map.Entry.comparingByValue())
              .map(Map.Entry::getKey)
              .orElseThrow(NoUniqueCharactersException::new);
  }

(wrong answer provided below, keeping it as a learning lesson...)

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.

StackExchange Code Review Q#112272, answer score: 4