Find Common Characters – Mahmoud Ashraf

1002. Find Common Characters 🔗

Date: Jun 05, 2024

Tags: hash-table

Description

Given a string array words, return an array of all characters that show up in all strings within the words (including duplicates). You may return the answer in any order.

Example 1:

Input: words = ["bella","label","roller"]
          Output: ["e","l","l"]

Example 2:

Input: words = ["cool","lock","cook"]
          Output: ["c","o"]

Constraints:

1 <= words.length <= 100
1 <= words[i].length <= 100
words[i] consists of lowercase English letters.

Optimal

function commonChars(words: string[]): string[] {
  const len = words.length;

  let prev: Record<number, number> = {};
  for (let i = 0; i < 26; i++) prev[i] = 0;

  const result: string[] = [];

  for (let i = 0; i < words[0].length; i++) {
    const code = words[0][i].charCodeAt(0) - 'a'.charCodeAt(0);
    prev[code]++;
  }

  for (let i = 1; i < len; i++) {
    const current: Record<number, number> = {};
    for (let i = 0; i < 26; i++) current[i] = 0;

    for (let j = 0; j < words[i].length; j++) {
      const code = words[i][j].charCodeAt(0) - 'a'.charCodeAt(0);
      current[code]++;
    }

    for (let j = 0; j < 26; j++) {
      current[j] = Math.min(current[j], prev[j]);
    }

    prev = current;
  }

  for (let i = 0; i < 26; i++) {
    const times = prev[i];
    const char = String.fromCharCode(i + 'a'.charCodeAt(0));

    for (let j = 0; j < times; j++) {
      result.push(char);
    }
  }

  return result;
}

export { commonChars };