Adjacent Characters Are Not the Same
Given a string containing lowercase English letters, rearrange its characters so that no two adjacent characters are the same.
If multiple valid rearrangements exist, return the lexicographically smallest one. If no valid rearrangement exists, return an empty string.
Rearrange String
Implement the following method:
String rearrangeString(String s)
Return the lexicographically smallest rearrangement in which every pair of adjacent characters is different. Return an empty string if such a rearrangement is impossible.
Behavior Requirements
- The returned string must contain exactly the same characters and frequencies as
s.
- For every valid index
i, the characters at i and i + 1 must be different.
- If multiple valid strings exist, return the lexicographically smallest one.
- Return an empty string when no valid rearrangement exists.
Constraints
1 ≤ s.length() ≤ 500s contains only lowercase English letters from 'a' to 'z'.
Examples
Example 1
rearrangeString(s = "aaabbc")
Output: "ababac"
Adjacent characters are different, and this is the lexicographically smallest valid rearrangement.
Example 2
rearrangeString(s = "aaaabb")
Output: ""
The four occurrences of 'a' cannot be separated using only two other characters.
Example 3
rearrangeString(s = "aabbcc")
Output: "abacbc"
Several valid rearrangements exist, and "abacbc" is the lexicographically smallest one.
Example 4
rearrangeString(s = "z")
Output: "z"
A string containing one character already satisfies the adjacency requirement.