First non repeating character in a string that doesn’t repeat is a popular problem for pupils. It sounds easy to find the “K’th” instance of such a character, but it gets harder when you have to do it. Many learners struggle to balance memory usage and speed when working with large datasets.
It’s quite important to know how to keep track of character frequencies and the sequence in which they appear. This article breaks down the logic into easy-to-understand phases, giving you the skills you need to quickly tackle this problem in a variety of programming languages.
Also Read – Advance Data Structure and Algorithms
What is First Non Repeating Character in a String ?
The purpose is to discover the K’th character in a string that only appears once. If the string is “chocolate” and K is 2, we first identify all characters that appear exactly once, then pick the second such character in order of appearance.
How to Find K’th Non Repeating Character
To solve this, we generally follow a two-pass strategy:
- Frequency Counting: Traverse the string to count how many times each character appears.
- Order Verification: Traverse the string (or a frequency map) again to identify which characters are unique and select the K’th one.
Also Read – Introduction to Red-Black Tree
Methods to Find First Non Repeating Character in a String
When searching for the first character with no repetition in a string, efficiency matters. Using a nested loop results in a time complexity of O(n²), which is too slow for large strings. Instead, we use a HashMap or a fixed-size array (for ASCII characters) to achieve O(n) time complexity.
| Method | Time Complexity | Space Complexity | Best For |
| Nested Loops | O(n²) | O(1) | Very small strings |
| Hash Map / Array | O(n) | O(1)* | General purpose & Interviews |
| OrderedDict (Python) | O(n) | O(n) | Maintaining insertion order |
*Space is O(1) if the character set is fixed (e.g., 256 for extended ASCII).
First Non Repeating Character in a String C++
In C++, we typically use an array of size 256 to store counts. This is highly memory-efficient as it avoids the overhead of complex data structures.
How to Find the first non repeating character in a string C++
To find the K’th character, we follow this logic:
- Create a count array and initialise it to zero.
- Loop through the string and increment the index corresponding to the character’s ASCII value.
- Loop through the string a second time. Check the count array. If the count is 1, decrement K.
- When K reaches zero, you have found your character.
Example Code Concept:
C++
// Logic for C++ implementation
int count[256] = {0};
for (int i = 0; i < str.length(); i++) count[str[i]]++;
int uniqueCount = 0;
for (int i = 0; i < str.length(); i++) {
if (count[str[i]] == 1) {
uniqueCount++;
if (uniqueCount == k) return str[i];
}
}
First Non Repeating Character in a String Java
In Java, we can use a HashMap for a more object-oriented approach or a simple array for performance. The logic remains consistent: track the frequency and then locate the K’th occurrence.
Also Read – Geometric Algorithms
How to Find the first non repeating character in a string Java
In Java, it’s smart to use a LinkedHashMap since it keeps the order in which items were added. In DSA rounds, though, a normal two-pass method with an array is frequently favoured because it is faster.
Key Steps for Java:
- Use str.toCharArray() to work with the input.
- Put frequencies in an int[] array.
- Go through the list and find the K’th unique element.
First Non Repeating Character in a String Python
Python offers elegant ways to solve this, such as using collections. Counter or list comprehensions.
How to find the first non repeating character in a string Python
Python’s OrderedDict is quite helpful here because it keeps track of the order in which keys were initially added. This lets us skip the second time we go through the original string and go through the dictionary instead.
Python Strategy:
- Use Counter(input_string) to count how many times something happens.
- Filter the characters that have a count of exactly 1.
- Index into the filtered list to find the K’th element.
Using list comprehension, this can be written in just a few lines, making it highly readable for developers.
First Non Repeating Character in a String Summary
The two-pass strategy works well, but we can make the solution even better by employing a single traversal.
How it works:
- Keep a map of frequencies
- Use a queue to keep track of possible characters that don’t repeat
- Once characters repeat, take them out of the queue.
This method doesn’t need to go over the string again, which is extremely helpful when streaming.
Algorithm to Find First Non Repeating Character in a String
To make sure you can do this under pressure, let’s look at the improved manual process:
- Set up an empty data structure: This might be a HashMap or an array with 256 elements.
- Fill in the structure: Scan the string from the left to the right. Add one to the value of a character every time you see it in your map or array.
- Find people that might be good candidates: Search for characters that appear once. These are the characters that don’t repeat.
- Select the K’th occurrence: Start another scan of the string. The first time you hit a character with a frequency of 1, that is the “first non-repeating character.” The second time is the second, and so on, until you reach K.
- Handle Edge Cases: If K is greater than the total number of unique characters, return an error message or a null value.
Edge Cases in First Non Repeating Character Problems
Handling edge cases correctly is essential:
- If K is greater than the number of non-repeating characters, return -1
- If no non-repeating character exists, return -1
- If the string is empty, return -1
- If all characters repeat, return -1
Why Order is Important in Non Repeating Character Problems
A common mistake is to sort the frequency map. Sorting destroys the original sequence of the string. Since the problem asks for the K’th character as it appears in the string, you must maintain the original indexing. This is why the second pass must be over the original string or an ordered collection.
Time and Space Complexity in Non Repeating Character
While O(n) is the standard time complexity, the “space” can vary. If you are working with Unicode characters (like Emojis or special symbols), a simple array of 256 will not suffice. In such cases, a HashMap is mandatory as it grows dynamically to accommodate unique keys.
First Non Repeating Character in a String Example
Input String: “success.”
K: 2
- Frequencies: s:3, u:1, c:2, e:1.
- Unique Characters: u, e.
- 1st Unique: u.
- 2nd Unique (K=2): e.
Output: e.
K’th Non-Repeating Character Key Takeaways
- The first character with no repetition in a string is simply the K=1 case of this problem.
- Hashing is the best way to find the right balance between speed and complexity.
- To avoid out-of-bounds problems, always check if K is greater than the number of unique characters.
FAQs
What is the quickest way to find the first character in a string that doesn't repeat?
Using a frequency array (for ASCII) or a HashMap in a two-pass algorithm is the fastest way. This makes sure that the time complexity is O(n), which means that the time it takes grows linearly with the length of the string.
If a string comprises spaces, how do I get the first character that doesn't repeat in C++?
The logic remains the same. The frequency array will count spaces like any other character because they have an ASCII value of 32. Add an if(str[i] != ' ') condition during the count and check phases if you wish to ignore gaps.
Can I find the non repeating character in a string in Java using a single pass?
While a standard two-pass is common, you can use a LinkedHashMap to store the count and the first seen index. After one pass, you go across the map again to find the K'th entry that has a count of 1.
What happens if K is larger than the number of unique characters?
In most implementations, you should return a specific value like -1 or a message saying "Not found." Always validate the value of K against the total count of unique characters identified.
Why is Python often used for the first non repeating character?
Python is popular because of its built-in libraries, such as collections.counter. These tools allow you to write the entire logic in very few lines of code compared to C++ or Java, which is helpful in fast-paced coding rounds.