Rearrange String to Avoid Adjacent Duplicates

amazon Given a string s containing only lowercase letters, rearrange the characters such that no two adjacent characters are the same. Return any valid result string or an empty string if such arrangement is not possible. For example, given: s = "aab", return "aba". Example Input aab