Rearrange characters in a string so that no character repeats consecutively.
Below are some of the test strings with their expected output.
Input: aaabc
Output: abaca
Input: aa
Output: No valid output
Input: aaaabc
Output: No valid output
Logic :
- Create frequency map of the given string
- Place the first character at indices 0, 2, 4, 6, ...,18, 20 etc., so that occurrences of the character are never together.
- Place the second character at indices 22, 24, 26, etc.
- Upon reaching the end of the array, we would wrap around and start filling odd indices, like 1, 3, 5, in that order