• 0

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

Solution :