In this tutorial, we will be exploring how to efficiently finding the first non-repeating character in a string using Java. This is a popular problem found on Leetcode. You may find the original challenge here: Leetcode Challenge - First Unique Character in a String
Step-by-Step Solution:
- Create a Map to store the frequencies of each character
- Iterate through the string and add each character to the map, incrementing the count each time you find a duplicate
- Iterate through the string a second time and check the frequencies stored in the map. The FIRST character you find with a count of 1 will be the first unique character.
You can find a helpful visual depiction of the solution strategy here.
To implement this solution in Java, we want to create two separate for
loops. The first loop will iterate through the string and store the frequency of each character in a HashMap
. We can do this using a simple put()
or get()
method in Java.
Here's an example of how you might iterate through the string and store the frequencies in the HashMap
:
String s = "leetcode";
Map<Character, Integer> frequencies = new HashMap<Character, Integer>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (frequencies.containsKey(c)) {
frequencies.put(c, frequencies.get(c) + 1);
} else {
frequencies.put(c, 1);
}
}
Once you have stored the frequencies of each character, you can then loop through the string again, this time checking for characters that have a count of 1
in the HashMap
:
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (frequencies.get(c) == 1) {
System.out.println("The first unique character is: " + c);
break;
}
}
FAQs
What data structure do I need to use?
A HashMap
or Dictionary
is a great data structure to use for this problem, since it allows us to store and access values quickly and in constant time.
How can I keep track of the frequencies of each character?
In order to keep track of the frequencies of each character, we use a Map (HashMap
or Dictionary
) to store the characters as keys, and their frequencies as values. Each time we iterate through the string and find a character, we update its frequency value in the map.
What if there are multiple unique characters?
If there are multiple unique characters in the string, then the solution above will return the first unique character it finds.
What if there are no unique characters?
If there are no unique characters in the string, then the solution above will not return any characters.