Hand of Straights

from collections import Counter

def is_n_straight_hand(hand, size):
    if len(hand) % size:
        return False
    count = Counter(hand)
    for start in sorted(count):
        while count[start] > 0:    # smallest left
            for card in range(start, start + size):
                if count[card] == 0:
                    return False   # a gap
                count[card] -= 1
    return True

Hand of Straights. You're dealt a hand of cards and a group size. Can you split the whole hand into straights of that size: runs of consecutive cards, like three, four, five?

Take one, two, three, six, two, three, four, seven, eight, in groups of three. Yes: one two three, two three four, and six seven eight. But one to five in groups of four is a no: five cards can't split into fours.

The naive way tries every way to split the cards, backing up when a group fails. The choices multiply, so that's exponential.

Here's the greedy trick. Look at the smallest card left. Nothing smaller is left to come before it, so it must start a straight. Take it and the next cards up, one of each. If one is missing, the answer is false. Repeat until the hand is empty.

In code: if the hand doesn't split evenly, return false. Count the cards, and visit the values in sorted order. While a value has copies left, it starts a straight: take one of each card up to the group size. If one has run out, return false. Otherwise, return true.

Let's deal it. Count each card: a single one, two twos, two threes, and one each of four, six, seven and eight. The smallest is one: take one, two, three. Now the smallest is two: take two, three, four. The threes and fours are gone, so next is six: take six, seven, eight. Every pile is empty: true.

Sorting the values takes n log n time, and each card is taken just once. The counts take n space.

Smallest card first, build the straight, stop at a gap. That's Hand of Straights.