SRM496 - div2 - level one

srm496_div2_level1.py

#! /usr/bin/env python
# -*- coding: utf-8 -*-

"""SRM496 - div2 - level one

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 S, return the 
size of its largest anagram-free subset. Note that the entire set is 
considered a subset of itself.

Definition: 
    Class: AnagramFree
    Method: getMaximumSubset
    Parameters: String[]
    Returns: int
    Method signature: int getMaximumSubset(String[] S)
"""

class AnagramFree(object):
    """Anagram Free

    Constraints:
        - S will contain between 1 and 50 elements, inclusive.
        - Each element of S will contain between 1 and 50 characters, inclusive.
        - Each element of S will consist of lowercase letters ('a'-'z') only.
        - All elements of S will be distinct.

    >>> anagram = AnagramFree()
    >>> print anagram.getMaximumSubset(["abcd","abdc","dabc","bacd", ])
    1
    >>> print anagram.getMaximumSubset(["abcd","abac","aabc","bacd", ])
    2
    >>> print anagram.getMaximumSubset(
    ...     ["aa","aaaaa","aaa","a","bbaaaa","aaababaa", ])
    6
    >>> print anagram.getMaximumSubset(
    ...     ["creation","sentence","reaction","sneak","star","rats","snake", ])
    4
    """

    def __init__(self):
        pass

    def getMaximumSubset(self, S):
        def sort(word):
            chars = list(word)
            chars.sort()
            return ''.join(chars)

        subset = set()
        for word in S:
            for check in [check for check in S if check != word]:
                _word = sort(word)
                if _word not in subset or _word != sort(check):
                    subset.add(_word)
        return len(subset)

if __name__ == '__main__':
    import doctest
    doctest.testmod()