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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
/* * @Author: Ajk Palikuqi * * @Question: How To Find The First Non Repeated Character In A String * */ package iqLib.stringLib; import java.util.Arrays; public class NonRepeatedChar { public final static int MAX_CHAR_NUMBER = 256; public static int FindFirstNonRepeatedChar1(String fooBar) { char[] tempCharArray = fooBar.toCharArray(); Arrays.sort(tempCharArray); if (fooBar.length() == 1) { return 0; } for (int i = 0; i < fooBar.length(); ++i) { int idx = Arrays.binarySearch(tempCharArray, fooBar.charAt(i)); if ((idx == tempCharArray.length - 1) || tempCharArray[idx] != tempCharArray[idx+1]) { return idx; } } // Non-dupe char not found return -1; } } |
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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
/* * @Author: Ajk Palikuqi * * @Question: How To Find The First Non Repeated Character In A String * */ package iqLib.stringLib; import java.util.Arrays; public class NonRepeatedChar { public final static int MAX_CHAR_NUMBER = 256; public static int FindFirstNonRepeatedChar2(String fooBar) { int[] cachedChars = new int[MAX_CHAR_NUMBER]; // Initialize the array with 0s for (int i = 0; i < MAX_CHAR_NUMBER; ++i) { cachedChars[i] = 0; } int length = fooBar.length(); // Fill the cache for (int i = 0; i < length; ++i) { cachedChars[fooBar.charAt(i)]++; } // Check for non dupes for (int i = 0; i < length; ++i) { if (cachedChars[fooBar.charAt(i)] == 1) { return i; } } // Non-dupe char not found return -1; } } |
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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
/* * @Author: Ajk Palikuqi * * @Question: How To Find The First Non Repeated Character In A String * */ package iqLib.stringLib; import java.util.LinkedHashMap; import java.util.Map; public class NonRepeatedChar { public final static int MAX_CHAR_NUMBER = 256; public static int FindFirstNonRepeatedChar3(String fooBar) { Map<Character, Boolean> cacheChars = new LinkedHashMap<Character, Boolean>(); int length = fooBar.length(); for (int i = 0; i < length; ++i) { Character currKey = new Character(fooBar.charAt(i)); cacheChars.put(currKey, !cacheChars.containsKey(currKey)); } for (Map.Entry<Character, Boolean> entry : cacheChars.entrySet()) { if (entry.getValue()) { return fooBar.indexOf(entry.getKey()); } } return -1; } } |
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 🙂
Latest posts by Ajk (see all)
- Find Median from Numbers Array - January 1, 2018
- Find Whether a Number Can Be the Sum of Two Squares - August 12, 2017
- How to Find Two Primes Whose Sum is Equal to a Number N - April 22, 2017