6
\$\begingroup\$

Problem Statement :

Print the first non repeating character in a string.

Example :

In the string somecharsjustdon'tliketorepeat, m is the first non-repeating charecter.

My attempt :

New Code : Old one was not working as expected so I have updated the post. Old code can be found below new code

public class FirstNonRepeatedChar{
    static boolean isRepeated(String str, char c){
        int count = 0;
        for(char ch: str.toCharArray()){
            if(c == ch){
                count++;
            } 
        }
        
        return count > 1;
    }
    
    static void printFirstNonRepeatedChar(String str){
        boolean found = false;
        
        for(char c : str.toCharArray()){
            
            if(! isRepeated(str, c)){
                found = true;
                System.out.println(str + " : " +c);
                break;
            }
        }
        
        if(!found){
            System.out.println(str + " : No non-repeated char");
        }
    }
    
    public static void main(String [] args){
        String []testCases = {"aaabbcc", "sss", "121", "test", "aabc"};
        
        for(String str: testCases){
            printFirstNonRepeatedChar(str);
        }
    }
}

Old code

public class FirstNonRepeatedChar{

    public static void main(String [] args){
        String str = "somecharsjustdon'tliketorepeat";
        
        loopI:
        for(int i = 0;i<str.length();i++){
            for(int j = i+1; j<str.length();j++){
                if(str.charAt(i)==str.charAt(j))
                    continue loopI;
            }
            System.out.println(str.charAt(i));
            break;
        }
    }
}

I want to ask :

  • Is there better way to solve this problem? Especially, is there efficient way to do this using built-in classes?
  • Can I reduce complexity?
  • Is there any case where my code may fail to generate appropriate result? and how can I avoid these failures?

Thanks in advance!

\$\endgroup\$
  • 1
    \$\begingroup\$ Try abab or ababx. Your alrogithm outputs a for both of them, where no output and x is expected respectively. Use an ordered map<char, count> to count the occurences of each character, then lookup the first character whose occurence is 1. \$\endgroup\$ – slepic Sep 25 at 7:06
  • \$\begingroup\$ @slepic, Thanks for your reply. I think i have made very silly mistakes. I'll try to solve it. Thanks for suggesting orderedmap I'll check that. \$\endgroup\$ – Omkar76 Sep 25 at 7:16
  • 1
    \$\begingroup\$ Please fix the code and write some tests to make sure your code actually works. Also include the complete requirements to the question such as restrictions on input and such. I.e. post the exact assignment text. \$\endgroup\$ – TorbenPutkonen Sep 25 at 8:06
  • 1
    \$\begingroup\$ @TorbenPutkonen I have updated post to provide correct code. Sorry but I was not given any input restrictions or any other rules. \$\endgroup\$ – Omkar76 Sep 25 at 8:23
  • 1
    \$\begingroup\$ Now I have also added some test cases. \$\endgroup\$ – Omkar76 Sep 25 at 8:33
9
\$\begingroup\$

Welcome to Code Review. There are already excellent answers, I am adding an alternative solution running in \$O(n)\$ and relatively simple to understand.

private static void printFirstNonRepeatedChar(String str) {
    // LinkedHashMap maintains the insertion order
    Map<Character, Integer> freq = new LinkedHashMap<>();
    
    // Create map of frequencies   
    for (Character c : str.toCharArray()) {
        if (freq.containsKey(c)) {
            freq.put(c, freq.get(c) + 1);
        } else {
            freq.put(c, 1);
        }
    }
    
    // Find first character with frequency 1
    for (Entry<Character, Integer> entry : freq.entrySet()) {
        if (entry.getValue() == 1) {
            System.out.println(entry.getKey());
            break;
        }
    }
}

The map freq contains the frequencies of the characters. For example, given the string aabbc, the map will be:

  • a -> 2
  • b -> 2
  • c -> 1

LinkedHashMap maintains the insertion order so after building the map it's enough to find the first entry with frequency 1.

This is the same but using Streams:

private static Character findFirstNonRepeatedChar(String str) {
    Map<Character, Long> freq = str.codePoints()
            .mapToObj(c -> (char) c)
            .collect(Collectors.groupingBy(Function.identity(),
                                           LinkedHashMap::new, 
                                           Collectors.counting()));
    return freq.entrySet().stream()
            .filter(e -> e.getValue()==1)
            .map(Map.Entry::getKey)
            .findFirst().orElse(null);
}

Time complexity

Your solution runs in \$O(n^2)\$, where \$n\$ is the length of the input string. I highlighted in your code the relevant parts:

static void printFirstNonRepeatedChar(String str){
    // O(n)
    for(char c : str.toCharArray()){
        // isRepeated runs in O(n)
        if(! isRepeated(str, c)){
           // O(1)
        }
    }
    //..
}

As @Joop Eggen said, for small input strings you need to benchmark the solutions to really see the difference, but for large inputs the Big O notation must be considered.

Testing and reusability

Generally, it's better to return a result instead of printing in the method. It's easier to test and reuse. In your case the method could return the character or null. For example:

static Character printFirstNonRepeatedChar(String str){
    //...
        if(! isRepeated(str, c)){
            return c;
        }
        return null;
}

Now the method is easy to test:

@Test
public void findFirstNonRepeatedCharTest() {
    assertEquals(Character.valueOf('c'),findFirstNonRepeatedChar("aabbc"));
    assertNull(findFirstNonRepeatedChar("aa"));
}

Minor changes

  • In the method printFirstNonRepeatedChar you can just return; instead of using the flag found and break.
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ First of all thanks for warm welcomes Marc :) Very nice solution and explaination. It's easy to understand. codereview seems to best community so far ;). I'm confused whose answer to should I mark as best. All are good. \$\endgroup\$ – Omkar76 Sep 25 at 11:43
  • 1
    \$\begingroup\$ @Omkar76 I am glad I could help. My suggestion is to wait until the question is not "active" anymore, to be sure that you don't miss any other good review. Then pick the answer that is best for you ;) \$\endgroup\$ – Marc Sep 25 at 12:08
  • 1
    \$\begingroup\$ @Omkar76 FYI I added the solution using Java Streams and few other advices. \$\endgroup\$ – Marc Sep 26 at 9:58
  • 1
    \$\begingroup\$ Something to keep in mind is autoboxing, to a certain degree. Every time you assign a char to a Character, the compiler silently adds Character.valueOf(c), which might or might not give you a cached instance. Same goes for your unit test, instead of creating a new instance, you should call Character.valueOf. \$\endgroup\$ – Bobby Sep 26 at 14:24
  • \$\begingroup\$ @Bobby good point. And I just noticed that new Character() has been deprecated since Java 9. \$\endgroup\$ – Marc Sep 26 at 15:19
8
\$\begingroup\$

There are some weak spots, but an optimal algorith would need:

  • To check all characters for unique ones.

So:

Optional<Character> firstNonRepeatingChar(String s) {
    Set<Character> candidates = new LinkedHashSet<>();
    Set<Character> duplicates = new HashSet<>();
    for (char ch : s.toCharArray()) {
        if (!duplicates.contains(ch)) {
            if (!candidates.add(ch)) {
                candidates.remove(ch);
                duplicates.add(ch);
            }
        }
    }
    return candidates.stream().findFirst();
}

if (!duplicates.contains(ch)) treats a new candidate char or existing one. When !candidates.add(ch) the char already existed in candidates, hence we encountered a new duplicate.

This uses for candidate chars a LinkedHashSet which keeps the order of insertion. The return of findFirst hence will return the first added unique char.

At some time duplicates need to be removed from the candidates to find the solution. Here it is done immediately.

Note that add returns whether indeed added; else there was already such an element.

One might have used a Map<Character, Boolean> for both char states (isCandidate/isDuplicate).


  • isRepeated starts from 0, not utilising the position where you found c.
  • Calling toCharArray would create a char array, which will happen for every c.
  • When count reaches 2 one can return true.

Even when repairing this, the complexity is quadratic: O(N²).

My solution would be: O(N.log N) as one may assume log N for contains/adding/removing from a Set. Considerably better. Especially as HashSet is fast, almost O(1).


However

For small strings of say approx. 30 characters one would need benchmarking to determine the fastest algorithm. Data structures like Set are very valuable - also for code quality - but a brute force for-loop might still be faster.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thanks @Joop Eggen. Interesting approach. I got a bit confused looking at those if statements but overall nice solution. Thanks for pointing out my mistakes. I really appriciate that. \$\endgroup\$ – Omkar76 Sep 25 at 10:39
  • \$\begingroup\$ Interesting. Compared to @Marc's answer using one LinkedHashMap to count occurrences (and then search it for the first entry with a count of 1), this has the advantage of being read-only when scanning through already-duplicate characters, so it's great for long strings with a small alphabet (like English or ASCII). Although if you know you have ASCII, bool seen[256] and int firstpos[256] would remove the cost of hashing. \$\endgroup\$ – Peter Cordes Sep 25 at 21:20
  • \$\begingroup\$ Over a long string with a large alphabet with a mix of repeats and unique characters (where the answer appears fairly early in the string), Marc's might win: this answer would be removing from one set and adding to another for a lot of inputs, vs. just finding and incrementing counters. But that's probably the worst case for this answer. Also for small strings, one linkedhashmap might be cheaper to init and tear down than two sets (one of them linked). As you say, you'd need to benchmark for any given use-case if it was a significant time sink or source of GC churn. \$\endgroup\$ – Peter Cordes Sep 25 at 21:26
  • \$\begingroup\$ Something to keep in mind is autoboxing here. Ever time you use a char as Character, the comiler silently adds a call to Character.valueOf, which might or might not give you a cached instance. \$\endgroup\$ – Bobby Sep 26 at 14:25
7
\$\begingroup\$

One point I don't find addressed in Joop Eggen's answer:

My take is entirely similar to his, isolating determination of the result from use:

 /** @return first non-repeated <i>code point</i> from <code>str</code> */
    static Optional<Integer> firstNonRepeatedChar(CharSequence str) {
        Set<Integer>
            all = new java.util.LinkedHashSet<>(9 + Integer.highestOneBit(str.length())),
            repeated = new java.util.HashSet<>();
        str.codePoints().forEachOrdered(c -> {
            if (!all.add(c))
                repeated.add(c); });
        all.removeAll(repeated);  // "all non-repeated" hereafter
        return all.stream().findFirst();
    }
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ +1 Thanks for help but your code is not compiling as all.removeAll() is returning boolean value. Please edit your code. \$\endgroup\$ – Omkar76 Sep 25 at 10:50
  • 1
    \$\begingroup\$ I find this answer compelling, especially as using int code points (UTF-32, pure Unicode numbers) is nice, IMHO state of the art, rather than char (UTF-16). You still might consider OptionalInt and then a better name firstUniqueCodePoint. \$\endgroup\$ – Joop Eggen Sep 25 at 10:57
  • \$\begingroup\$ (One of my problems is I didn't yet upgrade my local IDE from Java 8: infant streams, no Optional at all, … - lame excuse with all the web IDEs around.) (Hey, and Oracle ruined the use of their online-javadoc with firefox.) \$\endgroup\$ – greybeard Sep 25 at 11:17
  • \$\begingroup\$ (@JoopEggen Optional<Integer> has the advantage of being the type of Collection<Integer>.stream().findFirst(). I want(ed) to help making the connection to printFirstNonRepeatedChar().) \$\endgroup\$ – greybeard Sep 25 at 12:12
  • \$\begingroup\$ Why do you think that this method needs a documentation comment? Every word from that comment is already contained in the function signature, except for "Code Point", but that's due to the inappropriate method name. \$\endgroup\$ – Roland Illig Sep 26 at 11:23
3
\$\begingroup\$

I would do it without the additional set as follows. Basically same approach as here, but with a different return value.

public class FirstNonRepeatedChar {
    public static void main(String[] args) {
        System.out.println(findFirstNonRepeatedChar("somecharsjustdon'tliketorepeat"));
    }
    
    /**
     * Returns the first non-repeated char.
     * 
     * @param input
     * @return
     */
    private static char findFirstNonRepeatedChar(final String input) {
        final var len = input.length();
        for (var index = 0; index < len; index++) {
            final var ch = input.charAt(index);
            // find next index of that char
            final var firstIndex = input.indexOf(ch);
            final var lastIndex = input.lastIndexOf(ch);
            if (firstIndex == lastIndex) {
                // this means there is no next char
                return ch;
            }
        }
        // No such char found.
        return 0;
    }
}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Fine solution. Though complexity O(N²) it stops when the unique char is found, say in the beginning. So its actual speed can compare very good. And indexOf is ideal. \$\endgroup\$ – Joop Eggen Sep 25 at 11:55
  • 2
    \$\begingroup\$ This is one of the approaches I thought of but there is a trap! Your code is going to check for duplicates ahead of currecnt char so in case where there is no similar char ahead but there are some behind current char it'll fail. One such case will be "aasdds* - in second iteraion when loop checks for duplicates of second 'a' it won't find any ahead but there is one 'a' behind it. I hope it's clear what I'm trying to say. Thanks anyway :) \$\endgroup\$ – Omkar76 Sep 25 at 11:58
  • \$\begingroup\$ (one way to fix "the first/last occurrence problem" would be to compare firstIndexOf() to lastIndexOf() - with or without the current index as a parameter.) \$\endgroup\$ – greybeard Sep 25 at 12:17
  • \$\begingroup\$ I see the point. I admit it wasn't tested thoroughly. \$\endgroup\$ – Dorian Gray Sep 25 at 14:10
  • \$\begingroup\$ @greybeard Thanks, I updated my code. \$\endgroup\$ – Dorian Gray Sep 26 at 9:36

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.