[演算法題目] First Non-Repeating Character

本題資訊

難度：easy
使用語言：C++
相關概念：String

---

題目敘述

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.

Input:

string = "abcdcaf"

Output:

1

Idea 1

這題是問第一個不重複的字母。因為又和字母個數相關（大於等於 2 就是重複），所以很直覺想用 map。和其它題的方式一樣，先遍歷整個 string 並記錄好個數後，再走一次 string，並且過程中比對 map 是否有個數等於 1 的字母，若有則代表沒有重複，回傳該字母位置。

#include <unordered_map>
using namespace std;

int firstNonRepeatingCharacter(string string) {
  unordered_map<char, int> chCount;
  int index = 0;

  for (auto ch : string){
    chCount[ch]++;
  }
  for (auto ch : string){
    if (chCount[ch] == 1)
      return index;
    index++;
  }
  return -1;
}

時間複雜度：\(O(n)\)，\(n\) 是 string 長度。
空間複雜度：\(O(1)\)

空間複雜度的部份我原本想填的是 \(O(e)\)，\(e\) 是 string 中唯一的字母個數，但因為有限定是小寫字母，最多也不會超過 26 個，所以應該可以算是常數 \(O(1)\)？

Idea 2

另外一個想法就是由 ASCII code 著手！因為題目有字母，雖然要統計但也只是回傳第一個非重複字母位置。加上限定小寫字母，所以更適合使用此方法。

和上述 map 的做法大同小異，只不過不用 map，而是用更傳統的陣列。遍歷整個 string 並統計，依各個字母順序存在整數陣列中（例如 a 的個數就是在 chCount[0] 中）。再走一次 string，並且過程中比對是否有個數等於 1 的字母，若有則代表沒有重複，回傳該字母。

using namespace std;

int firstNonRepeatingCharacter(string string) {
  int chCount[26] = {0};
  int index = 0;

  for (auto ch : string){
    chCount[ch - 'a']++;
  }
  for (auto ch : string){
    if (chCount[ch - 'a'] == 1)
      return index;
    index++;
  }
  return -1;
}

時間複雜度：\(O(n)\)，\(n\) 是 string 長度。
空間複雜度：\(O(1)\)