Count Unique Anagrams

Edit PagePage History

JCSU Unit 5 Problem Set 2 (Click for link to problem statements)

Problem Highlights

• 💡 Difficulty: Medium
• ⏰ Time to complete: 20 mins
• 🛠️ Topics: Strings, Sets, Sorting

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Established a set (2-3) of test cases to verify their own solution later.
• Established a set (1-2) of edge cases to verify their solution handles complexities.
• Have fully understood the problem and have no clarifying questions.
• Have you verified any Time/Space Constraints for this problem?

• What is the goal of the problem?
  • Count the number of unique anagram groups from a list of strings.
• Are there constraints on input?
  • Strings may contain lowercase alphabets only. Input may be empty.

HAPPY CASE Input: words = ["eat", "tea", "tan", "ate", "nat", "bat"] Output: 3 Explanation: The words "eat", "tea", and "ate" are anagrams (group 1). The words "tan" and "nat" are anagrams (group 2). The word "bat" forms its own group (group 3).

EDGE CASE Input: words = [] Output: 0 Explanation: An empty list results in 0 unique anagram groups.

EDGE CASE Input: words = ["a", "b", "c", "a"] Output: 3 Explanation: Each word forms its own group: "a" (unique), "b" (unique), "c" (unique).

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For anagram grouping problems, we want to consider the following approaches:

• Sorting and Sets: Normalize each word by sorting its characters, then use a set to track unique anagrams.
• Hash Maps (Alternative): Group anagrams by their character counts as keys.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea:
Normalize each word by sorting its characters. Add the normalized form to a set, as sets automatically handle duplicates. The size of the set will represent the number of unique anagram groups.

Steps:

1. Check if the input list words is empty. If so, return 0.
2. Initialize an empty set unique_anagrams to store unique normalized anagrams.
3. For each word in the list:
   • Normalize the word by sorting its characters and converting it to a tuple.
   • Add the normalized tuple to the set unique_anagrams.
4. Return the size of unique_anagrams.

4: I-mplement

Implement the code to solve the algorithm.

def count_unique_anagrams(words):
    if not words:  # Check if the input list is empty
        return 0  # Return 0 for an empty list

    unique_anagrams = set()  # Use a set to store unique normalized anagrams

    for word in words:
        # Normalize each word by sorting its characters and converting it to a tuple
        normalized = tuple(sorted(word))
        unique_anagrams.add(normalized)  # Add the normalized word to the set

    return len(unique_anagrams)  # The size of the set represents the count of unique anagrams

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

Example 1:

• Input: words = ["eat", "tea", "tan", "ate", "nat", "bat"]
• Expected Output: 3
• Observed Output: 3

Example 2:

• Input: words = []
• Expected Output: 0
• Observed Output: 0

Example 3:

• Input: words = ["a", "b", "c", "a"]
• Expected Output: 3
• Observed Output: 3

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume n is the number of words and m is the average length of a word.

• Time Complexity: O(n * m log m) because we sort each word (O(m log m)) for all n words.
• Space Complexity: O(n * m) because we store n normalized words in the set.