Editorial for CCC '16 S1 - Ragaman


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

by Timothy Li

First, count the number of occurrences of each letter in the first string. Then, count the number of each letter and number of wildcards in the second string. If the second string has more of a letter than the first string, it cannot be a wildcard anagram no matter what. If the second string has less of a letter than the first string, we need to use wildcards to substitute for those. In fact, we will always have enough wildcards as long as the two strings are the same length. Therefore, the answer is A if and only if the count of each letter in the second string is less than or equal to the count of the corresponding letter in the first string.

Complexity: \mathcal{O}(N)

Solution — Python 2

import string
A = raw_input()
B = raw_input()
for letter in string.ascii_lowercase:
    if A.count(letter) < B.count(letter):
        print 'N'
        break
else:
    print 'A'

Comments

There are no comments at the moment.