Common Characters

Tags

Common Characters

Category

Strings

Difficulty

Easy

Problem Statement

Given an array of strings, find all characters that are common to every string in the array. Return them as an array of single-character strings. If a character appears multiple times in every string, it should appear that many times in the result.

Intuition

A character is "common" if it exists in every single string. By counting character frequencies in each string and taking the minimum count across all strings for each character, we identify exactly which characters (and how many of each) appear in every string. This is essentially an intersection operation on character frequency maps.

Approach

  1. Build a character frequency map for the first string.
  2. For each subsequent string:
    • Build a frequency map for that string.
    • For each character in the running frequency map, update its count to the minimum of its current count and its count in the new string's map (0 if absent).
  3. After processing all strings, construct the result array by adding each character the number of times indicated by its final count.

Pseudocode

function commonCharacters(strings):
    if strings is empty:
        return []

    commonFreq = frequencyMap(strings[0])

    for i from 1 to length(strings) - 1:
        currentFreq = frequencyMap(strings[i])
        for char in commonFreq:
            commonFreq[char] = min(commonFreq[char], currentFreq.getOrDefault(char, 0))

    result = []
    for char, count in commonFreq:
        for j from 0 to count - 1:
            result.append(char)

    return result

Time & Space Complexity

  • Time: O(n * m) where n is the number of strings and m is the length of the longest string. We build a frequency map for each string.
  • Space: O(c) where c is the number of unique characters (bounded by the alphabet size, so effectively O(1) for lowercase English letters).

Key Insights

  • Using the minimum frequency across all strings correctly handles duplicate characters.
  • The problem reduces to frequency map intersection.
  • Since we only deal with characters, the space for frequency maps is bounded by the alphabet size (e.g., 26 for lowercase English).

Edge Cases

  • Array with a single string: every character in that string is "common."
  • One string is empty: no characters are common, return an empty array.
  • All strings are identical: the result is all characters from that string.
  • Strings with no overlapping characters: return an empty array.
  • Characters that appear multiple times in all strings: include them the minimum number of times they appear in any single string.

Linked mentions