First non repeated character

Question

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!

Answer 1

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.

Answer 2

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.

Answer 3

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

• don't write, never present un(doc)commented code

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();
    }

Answer 4

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;
    }
}