All problems

Reorganise String

Medium · heap

You are given letters, a string of lowercase English letters. You may put its letters in any order you like, but you must use every letter exactly once.

A word is called *calm* if no two letters that sit next to each other are the same.

Return true if the letters can be rearranged into a calm word, and false if every possible arrangement has at least one pair of equal neighbours.

Examples

Example 1

Input: letters = "aab"

Output: true

The letters can be arranged as aba, where no two neighbours match.

Example 2

Input: letters = "aaab"

Output: false

Three a's need at least two other letters between them, and there is only one b.

Example 3

Input: letters = "aabbcc"

Output: true

For example abcabc.

Constraints

• 1 <= len(letters) <= 10^4
• letters contains only lowercase English letters