Question

Write the following Python script:

Problem Statement

A string X is an anagram of string Y if X can be obtained by arranging all characters of Y in some order, without removing any characters and without adding new characters. For example, each of the strings "baba", "abab", "aabb" and "abba" is an anagram of "aabb", and strings "aaab", "aab" and "aabc" are not anagrams of "aabb".

A set of strings is anagram-free if it contains no pair of strings which are anagrams of each other. Given a set of strings words, return the size of its largest anagram-free subset. Note that the entire set is considered a subset of itself.

Constraints

• words will contain between 1 and 50 elements, inclusive
• Each element of words contains between 1 and 50 characters, inclusive
• Each element of words will consist of lowercase letters 'a' -- 'z' only
• All elements of words will be distinct

Check your code with these examples:

------------------------------------------
words = ["abcd","abdc","dabc","bacd"]
Returns: 1
All of the strings in words are anagrams of each other, so no two of them can simultaneously belong to an anagram-free set.

------------------------------------------

words = ["a"]

Returns: 1

------------------------------------------

words = ["z"]

Returns: 1

------------------------------------------

words = ["abcd","abac","aabc","bacd"]

Returns: 2

One of the maximum anagram-free subsets is ["abcd","abac"].

------------------------------------------
words: ["aa","aaaaa","aaa","a","bbaaaa","aaababaa"]

Returns: 6

Note that strings of different length cannot be anagrams of each other.

------------------------------------------

words = ["creation","sentence","reaction","sneak","star","rats","snake"]

Returns: 4

Answer 1

Program Code Screenshot



Program Sample Console Input/Output Screenshot



Program Code to Copy

# Algorithm
# Sort each word by characters
# sort the word array
# remove all duplicates from the word array
def largestAnagramSubset(words):
    # Sort each word by characters
    for i in range(len(words)):
        words[i] = ''.join(sorted(words[i]))

    # sort words
    words.sort()

    # remove duplicates
    cur = 1
    while(cur < len(words)):
        if(words[cur] == words[cur-1]):
            words.pop(cur)
        else:
            cur += 1

    return len(words)

# demo


print("words = [\"abcd\", \"abdc\", \"dabc\", \"bacd\"]\nReturns:",
      largestAnagramSubset(["abcd", "abdc", "dabc", "bacd"]), "\n")

print("words = [\"a\"]\nReturns:", largestAnagramSubset(["a"]), "\n")

print("words = [\"z\"]\nReturns:", largestAnagramSubset(["z"]), "\n")

print("words = [\"abcd\",\"abac\",\"aabc\",\"bacd\"]\nReturns:",
      largestAnagramSubset(["abcd", "abac", "aabc", "bacd"]), "\n")

print("words = [\"aa\",\"aaaaa\",\"aaa\",\"a\",\"bbaaaa\",\"aaababaa\"]\nReturns:",
      largestAnagramSubset(["aa", "aaaaa", "aaa", "a", "bbaaaa", "aaababaa"]), "\n")

print("words = [\"creation\",\"sentence\",\"reaction\",\"sneak\",\"star\",\"rats\",\"snake\"]\nReturns:",
      largestAnagramSubset(["creation", "sentence", "reaction", "sneak", "star", "rats", "snake"]), "\n")