problem

輸入為一個字串，其中字元都是小寫英文字母，回傳字串中第一個只出現一次的字元的索引值。如果所有字元都重複出現，則回傳 -1。

sample input:
string = 'abcdcaf'

sample output:
1 // 只出現一次的字元中，b 是第一個，索引位置為 1

solution 01

第一種解法是暴力解，就是遍歷過字串，將每個字元和所有其他字元比較，如果都沒有相同的則代表它為非重複字元。
步驟是：

1. 以 i 指向第一個字元。
2. 以 j 遍歷過其他所有字元進行比較，如果 i 不等於 j (指向不同字元)，且 string[i] 等於 string[j]，則代表字元重複出現。
3. 若有重複出現，則將 i 指向下一個字元，重複步驟 2。否則回傳 i。
4. 比較過所有字元，若都沒有回傳索引值，則回傳 -1。

字串長度為 n
time: O(n＾2)
space: O(1)

function firstNonRepeatingCharacter(string) {
  for (let i = 0; i < string.length; i++) {
    let duplicate = false;
    for (let j = 0; j < string.length; j++) {
      if (i !== j && string[i] === string[j]) duplicate = true;
    }
    if (!duplicate) return i;
  }
  return -1;
}

solution 02

另一種作法是利用 hash table 做記錄。
步驟是：

1. 從頭開始看過每個字元，若字元沒有在 hash table 中則將字元加進去，字元的出現次數加一。
2. 記錄完後，再遍歷過一遍字串，逐一查找每個字元的出現次數，回傳第一個次數為一的字元索引，若都沒有則最後回傳 -1。

字串長度為 n
time: O(n) 因為看過兩遍字串，時間為 2n，簡化為 n。
space: O(1) 這是因為題目已經確定輸入的字串只會包含 26 個小寫英文字母，也就是 hash table 中儲存的資料數量是有限的，可以視為只用常數空間。若輸入的字串可以包含任何字元，則空間為 O(n)。

function firstNonRepeatingCharacter(string) {
  const charFrequency = {};
  for (let char of string) {
    if (!(char in charFrequency)) charFrequency[char] = 0;
    charFrequency[char]++;
  }

  for (let i = 0; i < string.length; i++) {
    const char = string[i];
    if (charFrequency[char] === 1) return i;
  }
  
  return -1;
}