Approach #1: Brute Force [Accepted]

Intuition

We will repeatedly try to form a group (of size W) starting with the lowest card. This works because the lowest card still in our hand must be the bottom end of a size W straight.

Algorithm

Let's keep a count {card: number of copies of card} as a TreeMap (or dict).

Then, repeatedly we will do the following steps: find the lowest value card that has 1 or more copies (say with value x), and try to remove x, x+1, x+2, ..., x+W-1 from our count. If we can't, then the task is impossible.

Complexity Analysis

  • Time Complexity: , where is the length of hand. The factor comes from min(count). In Java, the factor becomes due to the complexity of TreeMap.

  • Space Complexity: .


Analysis written by: @awice.