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: introductory

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)**.5%1==0and sum(s.count(c)%2for c in set(s))<=len(s)**.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) ** .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))**.5 != int((len(letters))**.5):
        return False
    else:
        n = int((len(letters))**.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