Find Common Characters

The task is to return a list of all characters that show up in all strings within the given list of words.

Let’s use a hashmap to keep count of character occurrences in each word and then find the minimum count for each character across all words, because that’s the maximum number of times that character can be in the result.

Here is the Python code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def commonChars(self, words: List[str]) -> List[str]:
        # Initialize the counts for the first word
        counts = collections.Counter(words[0])

        # Update counts for each word
        for word in words[1:]:
            counts &= collections.Counter(word)

        # Convert the counts to a list of characters
        return list(counts.elements())

In the above code:

• We first initialize a Counter for the first word in words. This Counter (counts) keeps track of the count of each character in the first word.
• For each subsequent word in words, we update counts to be the intersection of the current counts and the Counter of the current word. This operation updates counts to have the minimum count of each character across the two words.
• After iterating over all words, counts will hold the minimum count of each character across all words. So, the characters that are in all words will have a count greater than 0 in counts.
• The elements method of Counter returns an iterator over elements repeating each as many times as its count. So we convert this iterator to a list and return it.

The time complexity of this solution is O(n*m), where n is the number of words and m is the average length of the words.

The counts variable after the for loop in the solution only contains characters that are common in all the words.

When we take the intersection (&) of two Counter objects, it results in a new Counter with the minimum count for each element across the two Counters. So if a character is not in a word, its count in the Counter for that word is 0, and hence, the count in the intersection is also 0.

After the for loop, for each character in the counts variable, the count is the minimum count of that character across all words. So if a character is not in any one of the words, its count is 0, and it is not included in the elements() call. Hence, counts.elements() only includes characters that are common in all words.

The & operator is used for the intersection operation, but it doesn’t work directly with strings. It works on collections where elements are hashable, like sets, frozensets, and Counter objects in Python.

When used with two Counter objects, the & operator returns a new Counter with the minimum of each element’s count. This makes it useful for finding common elements between collections.

Here’s a quick demonstration:

1
2
3
4
5
6
7

from collections import Counter

counter1 = Counter('abracadabra')  # Counter({'a': 5, 'b': 2, 'r': 2, 'c': 1, 'd': 1})
counter2 = Counter('cadabraarc')   # Counter({'a': 5, 'r': 2, 'c': 2, 'd': 1, 'b': 1})

intersection = counter1 & counter2
print(intersection)  # Counter({'a': 5, 'r': 2, 'b': 1, 'c': 1, 'd': 1})

As you can see, the resulting Counter (intersection) has the common elements from both counter1 and counter2 with the count being the minimum count from the two counters. So, effectively, the & operator helped us find the intersection of the two counters.

Sure, here’s how you could structure the four exercises:

Exercise 1 - Understanding the Counter

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

# Import the required module
from collections import Counter

def count_elements(word):
    # Create a counter of the word
    counter_word = Counter(word)

    # Return the counter
    return counter_word

# Test the function
print(count_elements("hello"))  # Should return Counter({'l': 2, 'h': 1, 'e': 1, 'o': 1})

Exercise 2 - Performing Intersection of Counters

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

from collections import Counter

def intersect_counters(counter1, counter2):
    # Perform intersection operation
    intersection = counter1 & counter2

    # Return the intersection counter
    return intersection

# Test the function
print(intersect_counters(Counter("hello"), Counter("world")))  # Should return Counter({'l': 1, 'o': 1})

Exercise 3 - Getting Minimum Counter for all words

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

from collections import Counter

def get_min_counter(words):
    # Create initial counter with the first word
    min_counter = Counter(words[0])

    # Iterate over the rest of the words
    for word in words[1:]:
        # Perform intersection operation and update min_counter
        min_counter = min_counter & Counter(word)

    # Return the minimum counter
    return min_counter

# Test the function
print(get_min_counter(["hello", "world", "low"]))  # Should return Counter({'l': 1, 'o': 1})

Exercise 4 - Extracting Elements from Counter

1
2
3
4
5
6
7
8
9

def extract_elements(counter):
    # Extract elements from the counter
    elements = list(counter.elements())

    # Return the elements
    return elements

# Test the function
print(extract_elements(Counter({'l': 1, 'o': 1})))  # Should return ['l', 'o']

Each of these exercises focuses on a specific part of the final solution, allowing you to understand and practice each step separately. Once you’re comfortable with these, you can put them all together to solve the problem.

Alternative Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution:
    def commonChars(self, words: List[str]) -> List[str]:
        hash1 = [0]*26
        hash2 = [0]*26

        for ch in words[0]:
            hash1[ord(ch) - ord('a')] += 1

        for i in range(1, len(words)):
            for ch in words[i]:
                hash2[ord(ch) - ord('a')] += 1

            for i in range(26):
                hash1[i] = min(hash1[i], hash2[i])
                hash2[i] = 0

        ans = []
        for i in range(26):
            if hash1[i] > 0:
                count = hash1[i]
                while count:
                    x = chr(i + ord('a'))
                    ans.append(x)
                    count -= 1
        return ans

The given Python function commonChars from the Solution class returns a list of all characters that show up in all strings within the list words. This includes duplicates. If a character occurs in every string in words (including duplicates), it is part of the final list.

The function follows these steps:

1. Initialize Frequency Arrays: Two frequency arrays hash1 and hash2 are created, each of size 26 (for each lowercase English letter).

2. First Word Frequencies: The function calculates the frequency of each character in the first word and stores this in hash1.

3. Compare Frequencies: The function then iterates over the rest of the words. For each word, it calculates the character frequencies and stores them in hash2. It then compares hash1 and hash2, keeping the minimum frequency for each character. This is because we’re interested in characters that exist in all words, so we keep the smallest occurrence count.

4. Compile Answer: Finally, the function creates the answer list. For each character that exists in all words (i.e., has a frequency greater than 0 in hash1), the function appends that character (converted from its ASCII representation to a string) to the answer list.

The time complexity of this function is O(n), where n is the total number of characters in all words in the list, because each character is processed once.