# #5 First Non-Repeating Character
###### tags: `String` `Easy`
## Problem
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
```javascript
string = "abcdcaf"
```
### Sample Output
```javascript
1 // The first non-repeating character is "b" and is found at index 1.
```
<br>
:::spoiler **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.
```
:::
<br>
:::spoiler 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?
:::
<br>
:::spoiler 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?
:::
<br>
:::spoiler 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.
:::
<br>
<hr/>
## Solutions
### Official 1
```javascript=
// O(n^2) time | O(1) space - where n is the length of the input string
function firstNonRepeatingCharacter(string) {
for (let idx = 0; idx < string.length; idx++) {
let foundDuplicate = false;
for (let idx2 = 0; idx2 < string.length; idx2++) {
if (string[idx] === string[idx2] && idx !== idx2) foundDuplicate = true;
}
if (!foundDuplicate) return idx;
}
return -1;
}
```
<br>
### Official 2
```javascript=
// 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.
function firstNonRepeatingCharacter(string) {
const characterFrequencies = {};
for (const character of string) {
if (!(character in characterFrequencies)) characterFrequencies[character] = 0;
characterFrequencies[character]++;
}
for (let idx = 0; idx < string.length; idx++) {
const character = string[idx];
if (characterFrequencies[character] === 1) return idx;
}
return -1;
}
```
<br>
---
### Everyone's
#### Solution type 1
> Object 儲存 index，遍歷 Object 取 index 最小值
:::spoiler 東
```javascript=
// O(n) Time | O(1) space; n is length of input string
// space is O(1) since there's fixed number of lower case english alphabet
function firstNonRepeatingCharacter(string) {
const charMap = {};
for (let i = 0; i < string.length; i++) {
const currChar = string[i];
if (currChar in charMap) charMap[currChar] = false; //char 已存在就設定成 false
else charMap[currChar] = i;
}
const idxArr = Object.values(charMap).filter((val) => val !== false); //過濾不是 false 的 char
if (idxArr.length === 0) return -1;
return idxArr.reduce((acc, cur) => cur < acc ? cur : acc); //用 reduce 得到最小值
}
```
- `charMap[currChar]` 可以考慮將 `false` 改成 `-1`，以維持一種 data type
- `charMap[currChar] = false` (boolean)
- `charMap[currChar] = i` (number)
:::
:::spoiler Hao
```javascript=
const firstNonRepeatingCharacter = (str) => {
/**
* O(n) time, O(1) space
*/
const nonRepeatingCharRecords = {};
const repeatingCharRecords = {};
for (let idx = 0; idx < str.length; idx += 1) {
const char = str[idx];
if (repeatingCharRecords[char]); // 檢查 repeating
else if (char in nonRepeatingCharRecords) { // 檢查 nonRepeating
delete nonRepeatingCharRecords[char]; // 刪除 nonRepeating 的 key
repeatingCharRecords[char] = true; // 設定 repeating = true
}
else {
nonRepeatingCharRecords[char] = idx; //第一次出現
}
};
const idxs = Object.values(nonRepeatingCharRecords); //取出 nonRepeating 所有 value
if (!idxs.length) return -1;
else return idxs.reduce((firstShowIdx, idx) => Math.min(firstShowIdx, idx), Number.POSITIVE_INFINITY); //用 reduce 得到最小值
};
```
:::
:::spoiler SOL
```javascript=
// O(n) time | 0(n) space
function firstNonRepeatingCharacter(string) {
const countStorage = new Map();
for (const [i, character] of string.split("").entries()) {
countStorage.set(character, [...(countStorage.get(character) || []), i]); //把出現過的 char 的 index 存在 array 中
}
for (const [_, count] of countStorage) { //依序檢查 Map 中每個 count (array) 長度
if (count.length === 1) return count[0];
}
return -1;
}
```
:::
:::spoiler Raiy
```javascript=
// Time O(m+n) | Space O(n) ; n = length of the string, m = the character count of the string
function firstNonRepeatingCharacter(string) {
let stringArr = string.split('');
let alphabetMap = new Map();
for(let i = 0; i < stringArr.length; i++){
if(alphabetMap.has(stringArr[i])){
alphabetMap.set(stringArr[i], {only:false}); //char 出現第二次就設定 only: false
continue;
}
alphabetMap.set(stringArr[i], {only:true, index:i}); //保存出現的 char 的 index
}
for(const value of alphabetMap.values()){ //依序檢查 Map 中所有 value
if(value.only === true){
return value.index
}
}
return -1;
}
```
:::
:::spoiler 月
```javascript=
function firstNonRepeatingCharacter(string) {
/* Time O(n+c) Space O(c)
n is the length of the string.
c is the unique letter quantity of string.
*/
// -> Space: O(1)
const map = {};
for(const letter of string){
if(!(letter in map)){
map[letter] = 1;
}else{
map[letter] += 1;
}
}
for(const key in map){
if(map[key] === 1)return string.indexOf(key);
}
return -1;
}
```
- 可以考慮使用 Map，保證 key 的順序
:::
#### Solution type 2
> 遍歷兩次 string
:::spoiler YC
```javascript=
/*
time: O(n); - where n is the length of the string
space: O(1); - the constant space (the maximum number is 26 (English-alphabet letters))
*/
function firstNonRepeatingCharacter(string) {
const map = {}
for(const char of string){ //計算 char 出現次數
if(!(char in map)) map[char] = 0;
map[char]++;
}
for(let i=0; i < string.length; i++){ //依序遍歷 string 中的 char 並檢查 map
const char = string[i];
if(map[char] === 1) return i;
}
return -1;
}
```
:::
:::spoiler Becky
```javascript=
//time: O(n) | space: O(n) -> O(1)
function firstNonRepeatingCharacter(string) {
let map = {};
let len = string.length;
for(let letter of string){ //計算 char 出現次數
if(!map[letter]){
map[letter] = 0;
}
map[letter]++;
}
for(let i = 0; i < len; i++){ //依序遍歷 string 中的 char 並檢查 map
if(map[string[i]] === 1){
return i;
}
}
return -1
}
```
:::
<br>
---
## Supplement / Discussion
- space is O(1) since there's fixed number of lower case english alphabet
- key order
| | Map | Object |
| -------- | -------- | -------- |
| Key Order [(MDN)](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map) | The keys in Map are ordered in a simple, straightforward way: A Map object iterates entries, keys, and values in the order of entry insertion. | Although the keys of an ordinary Object are ordered now, this was not always the case, and the order is complex. As a result, it's best not to rely on property order.|
Sign in with Wallet
Connect another wallet