# First Non-Repeating Character

Uncover the method to quickly identify the first non-repeating character in a string for effective data processing.

Strings
easy

Published At

6/4/2021

Write a function that takes in a string of lowercase English-alphabet letters and returns the index of the string's first non-repeating character.

The first non-repeating character is the first character in a string that occurs only once.

If the input string doesn't have any non-repeating characters, your function should return -1.

### Sample Input

js
``string = "abcdcaf"``
js
``string = "abcdcaf"``

### Sample Output

js
``1 // The first non-repeating character is "b" and is found at index 1.``
js
``1 // The first non-repeating character is "b" and is found at index 1.``

### Hints

Hint 1

How can you determine if a character only appears once in the entire input string? What would be the brute-force approach to solve this problem?

Hint 2

One way to solve this problem is with nested traversals of the string: you start by traversing the string, and for each character that you traverse, you traverse through the entire string again to see if the character appears anywhere else. The first index at which you find a character that doesn't appear anywhere else in the string is the index that you return. This approach works, but it's not optimal. Are there any data structures that you can use to improve the time complexity of this approach?

Hint 3

Hash tables are very commonly used to keep track of frequencies. Build a hash table, where every key is a character in the string and every value is the corresponding character's frequency in the input string. You can traverse the entire string once to fill the hash table, and then with a second traversal through the string (not a nested traversal), you can use the hash table's constant-time lookups to find the first character with a frequency of 1.

Optimal Space & Time Complexity

O(n) time | O(1) space - where n is the length of the input string The constant space is because the input string only has lowercase English-alphabet letters; thus, our hash table will never have more than 26 character frequencies.

Solution-1
js
``````function firstNonRepeatingCharacter(string) {
for (let character of string) {
if (string.indexOf(character) == string.lastIndexOf(character)) {
return string.indexOf(character);
}
}
return -1;
}``````
Solution-1
js
``````function firstNonRepeatingCharacter(string) {
for (let character of string) {
if (string.indexOf(character) == string.lastIndexOf(character)) {
return string.indexOf(character);
}
}
return -1;
}``````
Solution-2
js
``````function firstNonRepeatingCharacter(string) {
for (let i = 0; i < string.length; i++) {
let found = false;
for (let j = i; j < string.length; j++) {
if (string[i] === string[j] && i !== j) found = true;
}
if (!found) return i;
}
return -1;
}``````
Solution-2
js
``````function firstNonRepeatingCharacter(string) {
for (let i = 0; i < string.length; i++) {
let found = false;
for (let j = i; j < string.length; j++) {
if (string[i] === string[j] && i !== j) found = true;
}
if (!found) return i;
}
return -1;
}``````

🦥

Do you have any questions, or simply wish to contact me privately? Don't hesitate to shoot me a DM on Twitter.

Have a wonderful day.
Abhishek 🙏

## Join My Exclusive Newsletter Community

Step into a world where creativity intersects with technology. By subscribing, you'll get a front-row seat to my latest musings, full-stack development resources, and exclusive previews of future posts. Each email is a crafted experience that includes:

• In-depth looks at my covert projects and musings to ignite your imagination.
• Handpicked frontend development resources and current explorations, aimed at expanding your developer toolkit.
• A monthly infusion of inspiration with my personal selection of quotes, books, and music.

Embrace the confluence of words and wonder, curated thoughtfully and sent straight to your inbox.

No fluff. Just the highest caliber of ideas.