Press "Enter" to skip to content

How to find the first non repeated character in a String

Ajk 0

Today thought I’d do a basic String question, since I have not done one in a while. How to find the first non repeated character in a String, is a classic.

So let’s think about it. As usual the most simple way is 2 iterations nested in each other, giving O(n2) runtime, bla bla bla, check my Strings are anagrams question for more info on this bad logic. The next thing that comes to mind after that is sorting. After all if we sort a String, we will have characters next to each other, and will just have to compare current char with the next char… Simple enough no?

Let’s get to some coding:

How to find the first non repeated character in a String – Java – Sorting

A quick glance at this will give us a O(1) auxiliary space complexity and O(nlog(n)) time complexity on the worst case scenario. Can we do better? Well we know with strings we can always cache based on different chars (i.e. ASCII has 256 chars, therefore we “only” need an array of fixed, 256 size to count and cache the amount of chars in any String. – Since an int takes 4 bytes, that is only 256 * 4 bytes = 1Kb… we can definitely afford that with today’s computers)

So let’s get again our heads to some code.

How to find the first non repeated character in a String – Java – Caching

Once again, we’ve done this many times, so I’ll just point out that our algorithm will take O(1) space and O(n) time! Pretty great eh? Well it turns out we want to gauge what inputs we’re having. For small Strings we’re still creating a 256 sized array… Big overhead. Me no likey.

Let’s try to use a map instead:

How to find the first non repeated character in a String – Java – Hashing and Caching

It’s important to note we can’t be sure of the Hashing lookup and insertion time (although it usually averages out and is assumed as O(1)). Noting that assumption, we can safely say that this algorithm will also perform like the previous one, but with less overhead in smaller values. Great, you safely and efficiently know how to find the first non duplicate char in a String in Java.

Hope you guys enjoyed this short post… and I’ll see you guys next time 🙂

The following two tabs change content below.
If you like one of my posts the best way to support is give it a thumbs up, comment, or share it on social media 🙂

Leave a Reply

Your email address will not be published. Required fields are marked *