364. Minimum Letter Sticker Sheet Design

Minimum Letter Sticker Sheet Design

A teacher needs letter stickers to make a given word.

Design a sticker sheet containing exactly stickersPerSheet lowercase letters. The teacher may use multiple identical copies of this sheet.

All copies together must provide each letter at least as many times as it appears in word. Extra stickers are allowed.

Minimize the number of sheet copies required. If several sheet designs require the same minimum number of copies, return the lexicographically smallest design.

Design a Letter Sticker Sheet

Implement the following method:

String designStickerSheet(String word, int stickersPerSheet)

Return a string representing the letters on one sticker sheet. Return "-1" if a valid sheet cannot be designed.

Requirements

Each character in the returned string represents one sticker on the sheet, and each sticker from each copy can be used at most once.
The returned string must contain exactly stickersPerSheet characters.
Every returned character must be a lowercase English letter.
Every copy of the sheet must have the same letters.
Extra letters that do not appear in word are allowed.
The number of sheet copies required must be as small as possible.
If several optimal designs exist, return the lexicographically smallest one.

Constraints

1 ≤ word.length() ≤ 100,000
word contains only lowercase English letters.
1 ≤ stickersPerSheet ≤ 100,000

Examples

Example 1

designStickerSheet(word = "letter", stickersPerSheet = 4)

Output: "elrt"

Two copies of "elrt" provide enough stickers for "letter". No design can provide all six required stickers using only one sheet.

Example 2

designStickerSheet(word = "mississippi", stickersPerSheet = 5)

Output: "aimps"

Four copies of "aimps" provide enough copies of 'm', 'i', 's', and 'p'. The extra position contains 'a' so that the design is lexicographically smallest.

Example 3

designStickerSheet(word = "garden", stickersPerSheet = 5)

Output: "-1"

The word requires six different letters, but one sheet has only five positions.

Example 4

designStickerSheet(word = "book", stickersPerSheet = 4)

Output: "bkoo"

One copy of "bkoo" contains exactly the letters needed for "book".