# First non repeated character

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


• 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?

• 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. Sep 25 '20 at 7:06
• @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. Sep 25 '20 at 7:16
• 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. Sep 25 '20 at 8:06
• @TorbenPutkonen I have updated post to provide correct code. Sorry but I was not given any input restrictions or any other rules. Sep 25 '20 at 8:23
• Now I have also added some test cases. Sep 25 '20 at 8:33

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(),
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.
• 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. Sep 25 '20 at 11:43
• @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 ;)
– Marc
Sep 25 '20 at 12:08
• @Omkar76 FYI I added the solution using Java Streams and few other advices.
– Marc
Sep 26 '20 at 9:58
• 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. Sep 26 '20 at 14:24
• @Bobby good point. And I just noticed that new Character() has been deprecated since Java 9.
– Marc
Sep 26 '20 at 15:19

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> duplicates = new HashSet<>();
for (char ch : s.toCharArray()) {
if (!duplicates.contains(ch)) {
candidates.remove(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.

• 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. Sep 25 '20 at 10:39
• 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. Sep 25 '20 at 21:20
• 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. Sep 25 '20 at 21:26
• 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. Sep 26 '20 at 14:25

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 -> {
all.removeAll(repeated);  // "all non-repeated" hereafter
return all.stream().findFirst();
}

• +1 Thanks for help but your code is not compiling as all.removeAll() is returning boolean value. Please edit your code. Sep 25 '20 at 10:50
• 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. Sep 25 '20 at 10:57
• (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.) Sep 25 '20 at 11:17
• (@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().) Sep 25 '20 at 12:12
• 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. Sep 26 '20 at 11:23

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

• 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. Sep 25 '20 at 11:55
• 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 :) Sep 25 '20 at 11:58
• (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.) Sep 25 '20 at 12:17
• I see the point. I admit it wasn't tested thoroughly. Sep 25 '20 at 14:10
• @greybeard Thanks, I updated my code. Sep 26 '20 at 9:36