Rearrange a String So Adjacent Characters Differ

Given a string s made up of lowercase English letters, reorder all of its characters into a new string such that equal characters never appear next to each other. If multiple valid strings exist, return the one that is lexicographically smallest. If no such string exists, return "". The result must be a permutation of s: every input character must appear exactly the same number of times in the output. Only the multiset of characters matters, not their original positions.…