easy Find Common Characters

Problem Statement

Given a strings array words, return a character array results containing all characters (including duplicates), which are common in all strings of words. You may return characters in any order.

Examples

• Example 1:

  • Input: words = ["glean","angle","angel","galen","lange"]
  • Expected Output: ["a","e","g","l","n"]
  • Justification: The letters 'a', 'e', 'g', 'l', and 'n' are present in all five words. Each of these letters appears at least once in every word, making them common to all strings.

• Example 2:

  • Input: words = ["danday","candya","ahand"]
  • Expected Output: ["a","a","d","n"]
  • Justification: The letters 'a', 'a', 'd', and 'n' are common in all three words, each appearing at least once in every word.

• Example 3:

  • Input: words = ["race","care","ac"]
  • Expected Output: ["a","c""]
  • Justification: The letters 'a', and 'c' are present in all three words. Each of these letters appears at least once in every word, so they are included in the output list.

Solution

To solve this problem, we'll adopt a character frequency mapping approach. The core idea is to create frequency maps for each string in the input list, tracking how often each character appears. Then, we'll compare these frequency maps to identify characters common to all strings, focusing on the minimum frequency of each character. This method ensures that we only include characters that appear in every string, and do so according to their least occurrence across all strings. This approach is effective because it directly addresses the problem's requirements, ensuring accuracy and efficiency by leveraging frequency counts to streamline comparisons and minimize unnecessary computations.

Our strategy involves iterating through each string in the input list, updating a global frequency map that reflects the minimum occurrences of each character across all strings examined so far. By starting with the first string's frequency map and adjusting it based on subsequent strings, we guarantee that only common characters with their minimum frequencies are retained. This method is chosen for its simplicity and effectiveness in handling varying string lengths and character distributions, ensuring a solution that is both scalable and adaptable to different input sizes.

Step-by-step Algorithm

1. Initialize a global frequency map (minFreq) with 26 elements, one for each letter of the alphabet, and set each value to the maximum integer value to represent the minimum frequency of each character across all strings.

2. Iterate over each word in the input array:

   • Create a local frequency map (charFreq) for the current word, initializing all values to 0.
   • For each character in the current word, increment its corresponding frequency in the local frequency map.
   • After processing the word, update the global frequency map by comparing it with the local frequency map. For each character, if its frequency in the local map is less than what's currently in the global map, update the global map with the local map's frequency.

3. After processing all words, iterate through the global frequency map:

   • For each character that has a frequency greater than 0, add it to the result list as many times as its frequency.

4. Return the result list containing all common characters with their minimum frequency.

Algorithm Walkthrough

Let's consider the input: words = ["race", "care", "ac"]

Initial Setup

• Global Map is initialized with infinity (or a very high number) for all alphabet characters to represent that we haven't encountered any characters yet.

Iteration 1: Processing "race"

• Local Map for "race": {'r':1, 'a':1, 'c':1, 'e':1}
• Global Map Update:
  • Since it's the first word, the Global Map is updated to match the Local Map of "race".
  • Global Map Now: {'r':1, 'a':1, 'c':1, 'e':1}

Iteration 2: Processing "care"

• Local Map for "care": {'c':1, 'a':1, 'r':1, 'e':1}
• Global Map Comparison and Update:
  • We compare each character's frequency in "care" with the Global Map.
  • Since all frequencies match and are not less than those in the Global Map, no update is needed.
  • Global Map Remains: {'r':1, 'a':1, 'c':1, 'e':1}

Iteration 3: Processing "ac"

• Local Map for "ac": {'a':1, 'c':1}
  • Note: 'r' and 'e' are not present in "ac", so their frequencies in the Local Map for "ac" are considered 0.
• Global Map Comparison and Update:
  • We update the Global Map based on the Local Map for "ac".
  • The characters 'r' and 'e' are not present in "ac", so their global frequencies are effectively set to 0 (or they are removed from consideration).
  • For 'a' and 'c', the frequencies in both the Global Map and the Local Map for "ac" match and are 1.
  • Global Map Now: {'a':1, 'c':1}
    • Only 'a' and 'c' remain with their frequencies unchanged because they are the only characters present in all words so far.

Final Result

• Global Map: {'a':1, 'c':1}
• The final result is derived from the Global Map, resulting in the characters ["a", "c"] as the common characters found in all input strings with the minimum frequency across all strings.

Code

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {

  // Finds common characters in all strings of an array
  public List<String> commonChars(String[] A) {
    int[] minFreq = new int[26];
    Arrays.fill(minFreq, Integer.MAX_VALUE); // Initialize min frequency with max values
    for (String word : A) {
      int[] charFreq = new int[26]; // Frequency of each character in the current word
      for (char c : word.toCharArray()) {
        charFreq[c - 'a']++; // Increment frequency
      }
      // Update global minimum frequency
      for (int i = 0; i < 26; i++) {
        minFreq[i] = Math.min(minFreq[i], charFreq[i]);
      }
    }

    List<String> result = new ArrayList<>();
    for (int i = 0; i < 26; i++) {
      while (minFreq[i]-- > 0) {
        result.add("" + (char) (i + 'a')); // Add common character to the result
      }
    }
    return result;
  }

  // Main method for testing
  public static void main(String[] args) {
    Solution solution = new Solution();
    String[][] examples = {
      { "glean", "angle", "angel", "galen", "lange" },
      { "danday", "candya", "ahand" },
      { "race", "care", "ac" },
    };
    for (String[] example : examples) {
      System.out.println("Input: " + Arrays.toString(example));
      System.out.println("Common Characters: " + solution.commonChars(example));
    }
  }
}

Complexity Analysis

Time Complexity

, where N is the number of strings in the array and L is the average length of a string.

• For each string, we count the frequency of each character, which takes time.
• We then iterate over the frequency array of length 26 (constant time, hence ignored in the complexity analysis) for each of the N strings to update the global minimum frequency counts.
• Therefore, the total time complexity is dominated by the iteration over each string and its characters.

Space Complexity

O(1), as we use a fixed-size integer array of length 26 to store the frequency of each letter from 'a' to 'z', which is a constant space requirement. Thus, the auxiliary space used by the algorithm is constant.