8
\$\begingroup\$

is being first and unique.

Challenge:

Write a program which finds the first non-repeated character in a string.

Specifications:

The first argument is a path to a file.
The file contains strings, one per line.
Print out the first non-repeated character of each string.

Solution:

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Map;
import java.util.LinkedHashMap;
import java.util.Scanner;

public class NoRepeat {
    public static void main(String[] args) throws FileNotFoundException {
        Scanner input = new Scanner(new File(args[0]));

        while (input.hasNextLine()) {
            System.out.println(
                retrieveFirstNonRepeatedLetter(input.nextLine())
            );
        }
    }

    public static char retrieveFirstNonRepeatedLetter(String input) {
        Map<Character, Boolean> letters = new LinkedHashMap<>();
        char firstNonRepeated = ' ';

        for (int i = 0; i < input.length(); i++) {
            char current = input.charAt(i);

            if (letters.containsKey(current)) {
                letters.put(current, false);
            } else {
                letters.put(current, true);
            }
        }

        for (Map.Entry<Character, Boolean> entry : letters.entrySet()) {
            if (entry.getValue() == true) {
                firstNonRepeated = entry.getKey();
                break;
            }
        }

        return firstNonRepeated;
    }
}

This solution is \$O(n)\$ but I get the feeling that it's far from the best possible way to accomplish this.

I thought maybe I should set it to account for upper and lower cases, but it wasn't specified (and 100% passed with this implementation).

Tests:

public class MyFirstUnitTest {
    @Test
    void toothyTest() {
        assertEquals('h', NoRepeat.retrieveFirstNonRepeatedLetter("tooth"));
    }

    @Test
    void smellyTest() {
        assertEquals('d', NoRepeat.retrieveFirstNonRepeatedLetter("odor"));
    }
}
\$\endgroup\$
  • \$\begingroup\$ How do you get to O(n^2)? Looks like O(n) to me. Which also makes sense, as even the very naive solution of taking the first letter and checking for duplicate, taking the second letter and checking for duplicate, ... and returning the first that doesn't should be O(n log n) in the worst case. \$\endgroup\$ – tim Mar 7 '15 at 19:58
  • \$\begingroup\$ I go through all the input character by character and put them in a map, then I go through the map to find the first entry whose value is 1. In the worst case, where there is no unique character, I'm looping through the entire data set twice. \$\endgroup\$ – Legato Mar 7 '15 at 20:03
  • 2
    \$\begingroup\$ right, thats 2*n which is equal to O(n) (and unequal to n*n which is O(n^2)). \$\endgroup\$ – tim Mar 7 '15 at 20:05
  • 1
    \$\begingroup\$ Just a note: ask a way to improve a \$O(n)\$ algorithm when you must at least read all data doesn't have too much sense. We are speaking about constants and if you would reduce constant you should profile your code... little bit overkill. \$\endgroup\$ – Michele d'Amico Mar 7 '15 at 20:54
  • \$\begingroup\$ I didn't think there'd be something better than O(n), just better than what I was doing(finding the value after the first loop). Thanks for your input. \$\endgroup\$ – Legato Mar 7 '15 at 20:58
6
\$\begingroup\$

This is on top of @tim's excellent review. I think this is a very good solution, and a clever use of LinkedHashMap. I can't think of a better or simpler algorithm.

Simplifications

This can be written simpler:

if (letters.containsKey(current)) {
    letters.put(current, false);
} else {
    letters.put(current, true);
}

Like this:

for (int i = 0; i < input.length(); i++) {
    char current = input.charAt(i);
    letters.put(current, !letters.containsKey(current));
}

Instead of comparing boolean expressions to true like this:

if (entry.getValue() == true) {

You can use them directly:

if (entry.getValue()) {

Unit tests

It's nice that you start adding unit tests. It will pay off!

To run your test cases in an IDE, you need to make them public (at least I had to, in IntelliJ).

As a small extra tip, to avoid long repeated calls like NoRepeat.retrieveFirstNonRepeatedLetter(...), sometimes it can be practical to create a helper method, for example:

void assertFirstNonRepeatedLetter(char expected, String string) {
    assertEquals(expected, NoRepeat.retrieveFirstNonRepeatedLetter(string));
}

@Test
public void toothyTest() {
    assertFirstNonRepeatedLetter('h', "tooth"); 
}

@Test
public void smellyTest() {
    assertFirstNonRepeatedLetter('d', "odor"); 
}

Why fall back to firstNonRepeated = ' ' ?

I suggest to pay close attention to the specs. It doesn't mention what should happen if there are no unique letters in the input. Don't assume arbitrary fallback values. The behavior is undefined, so it's kind of an illegal state. It's a good move to throw an IllegalStateException in this case:

public static char retrieveFirstNonRepeatedLetter(String input) {
    Map<Character, Boolean> letters = new LinkedHashMap<>();

    for (int i = 0; i < input.length(); i++) {
        char current = input.charAt(i);
        letters.put(current, !letters.containsKey(current));
    }

    for (Map.Entry<Character, Boolean> entry : letters.entrySet()) {
        if (entry.getValue()) {
            return entry.getKey();
        }
    }

    throw new IllegalStateException("No non-repeated characters");
}

And add a corresponding unit test to cover this:

@Test(expected = IllegalStateException.class)
public void nothingUnique() {
    NoRepeat.retrieveFirstNonRepeatedLetter("abab");
}
\$\endgroup\$
5
\$\begingroup\$

As I said in my comment, your code should run in O(n).

the first for loop is n, charAt is constant, containsKey is constant, the second for is again n, which leads to 2*n*c = O(n).

So timing wise your code does pretty well. I don't have many other complaints about it either, just a couple of small points:

  • it is generally recommended to work against interfaces, not implementations, and you do this with Map<Character, Boolean> letters = new LinkedHashMap<>();. The problem is that your implementation depends on the order that a LinkedHashMap provides, so you should actually use that, not the unordered Map.
  • current could be currentCharacter for more clarity.
  • in your last for loop, just return directly instead of breaking.
  • and then, if no letter was found, you should probably throw an exception (otherwise it will get confusing when is the actual result).
\$\endgroup\$
  • \$\begingroup\$ Thanks again for correcting me on the running time, I almost went that route as well, but I wasn't sure which Exception I would throw, is there any you would recommend? \$\endgroup\$ – Legato Mar 7 '15 at 20:28
  • \$\begingroup\$ @Legato not really. The IllegalStateException proposed by Janos sounds good, but the description doesn't really match. Java also has NoResultException, NotFoundException, and NoSuchElementException which sound ok, but the first is for database results, the second for webservices, and the third for iterators, so those don't really fit either. I would either create my own NoUniqueException, use IllegalArgumentException, or document really well that you return ' ' if nothing was found. \$\endgroup\$ – tim Mar 7 '15 at 20:34
  • \$\begingroup\$ @tim the last option is bad, because what if the first non-repeated character was a ' '? Then the user will be confused which one it meant. \$\endgroup\$ – TheCoffeeCup Mar 8 '15 at 4:01

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.