A [Word Square](https://en.wikipedia.org/wiki/Word_square) is a set of words written out in a square grid, such that the same words can be read both horizontally and vertically. The number of words, equal to the number of letters in each word, is known as the *order* of the square.

For example, this is an *order* `5` square found in the ruins of Herculaneum:

![](https://i.gyazo.com/e226262e3ada421d4323369fb6cf66a6.jpg)

Given a string of various uppercase `letters`, check whether a *Word Square* can be formed from it. 

Note that you should use each letter from `letters` the exact number of times it occurs in the string. If a *Word Square* can be formed, return `true`, otherwise return `false`.

__Example__

  * For `letters = "SATORAREPOTENETOPERAROTAS"`, the output should be
  `WordSquare(letters) = true`.
    It is possible to form a *word square* in the example above.

  * For `letters = "AAAAEEEENOOOOPPRRRRSSTTTT"`, (which is sorted form of `"SATORAREPOTENETOPERAROTAS"`), the output should also be
  `WordSquare(letters) = true`.

  * For `letters = "NOTSQUARE"`, the output should be
  `WordSquare(letters) = false`.
  
__Input/Output__

* [input] string letters

  A string of uppercase English letters.
  
  Constraints: `3 ≤ letters.length ≤ 100`.


* [output] boolean

  `true`, if a Word Square can be formed;
  
  `false`, if a Word Square cannot be formed.

Difficulty: EASY
Tags: Ad-hoc

Starter code:
def word_square(letters):
	

Solutions:
from collections import Counter

def word_square(ls):
	n = int(len(ls) ** 0.5)
	return n * n == len(ls) and sum((i % 2 for i in list(Counter(ls).values()))) <= n


def word_square(letters):
	root = int(len(letters) ** 0.5)
	return len(letters) ** 0.5 == root and sum([letters.count(i) % 2 for i in set(letters)]) <= root


from collections import Counter

def word_square(letters):
	N = len(letters) ** 0.5
	return not N % 1 and sum((v & 1 for v in Counter(letters).values())) <= N


def word_square(s):
	li = [s.count(i) for i in set(s)]
	t = sum((i for i in li)) ** 0.5
	return int(t) == t and sum((i & 1 for i in li)) <= t


word_square = lambda s: len(s) ** 0.5 % 1 == 0 and sum((s.count(c) % 2 for c in set(s))) <= len(s) ** 0.5


import math

def word_square(letters):
	length = int(math.sqrt(len(letters)))
	if length ** 2 != len(letters):
		return False
	dic = {}
	for i in letters:
		if i not in dic:
			dic[i] = 0
		dic[i] += 1
	odd = 0
	for i in dic:
		if dic[i] % 2 != 0:
			odd += 1
		if odd > length:
			return False
	return True


from collections import Counter

def word_square(letters):
	n = len(letters) ** 0.5
	if n != int(n):
		return False
	n = int(n)
	c = Counter(letters)
	(one, odd) = (0, 0)
	for i in c.values():
		if i == 1:
			one += 1
			odd += 1
		elif i != 1 and i % 2 != 0:
			odd += 1
	if one > n or odd > n:
		return False
	else:
		return True


from collections import Counter

def word_square(letters):
	sq = len(letters) ** 0.5
	if sq % 1 != 0:
		return False
	d = Counter(letters)
	return len([True for c in d if d[c] % 2 == 1]) <= sq


def word_square(letters):
	if len(letters) ** 0.5 != int(len(letters) ** 0.5):
		return False
	else:
		n = int(len(letters) ** 0.5)
	s = set(letters)
	(one, two) = (0, 0)
	for letter in s:
		if letters.count(letter) == 1:
			one += 1
		if letters.count(letter) == 2:
			two += 1
	return one <= n and two <= n ** 2 - n


def word_square(letters):
	l = [letters.count(x) for x in set(letters)]
	if int(len(letters) ** 0.5) ** 2 == len(letters):
		if sum((x for x in l if x == 1)) <= int(len(letters) ** 0.5):
			return True
		else:
			return False
	else:
		return False