problem

輸入為兩個字串 characters 和 document，一個包含可利用的字元，另一個代表要產生的文件。回傳是否可以以可用字元產生文件。

只有當某字元在可用字元中的出現次數 >= 文件中的出現次數，才算是可以產生文件。例如當 characters = 'abcabc', document = 'aabbccc'，應回傳 false，因為 characters 中還缺少一個 c。另外，document 中可能包含任何字元，例如特殊符號、大寫字母、數字、空白。

sample input:
characters = 'aheaollabbhb'
document = 'hello'

sample output:
true

solution 01

第一個作法是：

1. 迴圈過 document 字串。
2. 計算當前所在的字元在 document 中出現過幾次。
3. 計算該字元在 characters 中出現幾次。
4. 如果 characters 中的次數小於 document 中的次數，則回傳 false，否則回到步驟 2 計算下一個字元。

這個解法簡單但會做很多重複的計算，例如上方範例輸入中 'hello' 有兩個字母 'l'，就會經過兩遍一模一樣的計算。

如果 document 長度為 m，characters 長度為 n，這個解法的時間和空間複雜度為：
time: O(m * (m + n)) 迴圈 document 本身需要 m，而每迴圈過一個字元都要計算在兩個字串中出現的次數。
space: O(1)

function generateDocument(characters, document) {
  for (const currentChar of document) {
    let docCount = 0, charCount = 0;
    for (const char of document) {
      if (char === currentChar) docCount++;
    }
    for (const char of characters) {
      if (char === currentChar) charCount++;
    }
    if (docCount > charCount) return false;
  }
  return true;
}

或將計算字元出現次數的部分寫成另一個函式：

function generateDocument(characters, document) {
  for (const currentChar of document) {
    const docCount = countFrequency(currentChar, document);
    const charCount = countFrequency(currentChar, characters);
    if (docCount > charCount) return false;
  }
  return true;
}

function countFrequency(character, string) {
  let count = 0;
  for (const char of string) {
    if (char === character) count++;
  }
  return count;
}

solution 02

第二種解法嘗試優化第一種解，也就是步驟完全一樣，只是多記錄了已經計算過的字元。例如計算了第一個字元 h 之後，將它加進一個 set 之中，如果再碰到 h (或任何已經有在 set 中的字元) 就可以不用再重複計算。

這種方法的時間和空間複雜度為：
time: O(c * (m + n)) c 為 document 中不重複出現的字元數，c 基本上一定會小於 m，所以算是優化了第一種解的時間。
space: O(c)

function generateDocument(characters, document) {
  const counted = new Set();
  for (const currentChar of document) {
    if (counted.has(currentChar)) continue;

    const docCount = countFrequency(currentChar, document);
    const charCount = countFrequency(currentChar, characters);
    if (docCount > charCount) return false;

    counted.add(currentChar);
  }
  return true;
}

function countFrequency(character, string) {
  let count = 0;
  for (const char of string) {
    if (char === character) count++;
  }
  return count;
}

solution 03

第三種解再進一步減少重複的運算，嘗試只迴圈過一遍字串，過程中就計算所有字元的次數。而非每碰到一個字元就要迴圈過一遍字串。

這種作法利用 hash table 來作記錄，key 為字元，值為出現的次數。
步驟是：

1. 迴圈過 characters 字串。
2. 每一個字元若有在 hash table 中則次數加一，否則存進去。
3. 迴圈過 document 字串，查看每個字元若有在 hash table 中，則次數減一。如果次數已經被扣到 0，或不在記錄中，則回傳 false。

time: O(m + n)
space: O(c) 此處 c 為 characters 中不重複出現的字元數。

function generateDocument(characters, document) {
  const counts = {};
  for (let char of characters) {
    if (!(char in counts)) counts[char] = 0;
    counts[char]++;
  }
  for (let char of document) {
    if (!(char in counts) || counts[char] === 0) return false;
    counts[char]--;
  }
  return true;
}