Proficient Level
Implement the reorganizeStringPossible method that checks whether the string can be rearranged so adjacent characters differ.
The input is a string text.
Your task is to check whether the characters can be rearranged so that no two adjacent characters are the same.
For example, aab can be rearranged as aba, so the answer is true. But aaab cannot be rearranged without placing two a characters together, so the answer is false.
The key condition is the frequency of the most common character.
If one character appears too many times, there will not be enough other characters to separate its copies. For a string of length n, the maximum allowed frequency is (n + 1) / 2.
Count the frequency of each character and return false if any frequency is greater than this limit. Otherwise, a valid rearrangement is possible.
Pseudocode:
function reorganizeStringPossible(text):
n = length(text)
create empty frequency map
for each character ch in text:
frequency[ch]++
maxAllowed = (n + 1) / 2
for each character in frequency:
if frequency[character] > maxAllowed:
return false
return true