374. Rearrange Characters in a String Such That No Two Adjacent Are Same

Given a string s of lowercase English letters, determine whether its characters can be rearranged so that no two adjacent characters are the same. Print 'Yes' if such a rearrangement exists, 'No' otherwise.

Input: The input is a single line containing the string s of lowercase English letters. Output: Print 'Yes' if the characters can be rearranged so no two adjacent characters match, otherwise print 'No'.

1 <= |s| <= 10^5, s contains only lowercase English letters

Since this problem only asks for FEASIBILITY (not the actual rearranged string), the frequency-check shortcut avoids the more involved max-heap-based CONSTRUCTION technique needed for the related 'produce a valid rearrangement' variant of this problem.

Check whether a string's characters can be rearranged so no two adjacent characters are the same. Brute force: Try every possible permutation of the string's characters and check each one for adjacent duplicates - this is factorial time, wildly impractical, and completely unnecessary since a simple frequency check answers the yes/no question directly. Optimised: The mathematical fact that a valid no-adjacent-duplicates arrangement exists if and only if the most frequent character doesn't exceed ceil(n/2) lets you skip constructing any actual arrangement entirely - a single frequency count and one comparison settles the question in linear time.

Count the frequency of each character in a single linear pass (a 26-slot array), then find the maximum frequency among them. A valid no-two-adjacent-same arrangement exists if and only if that maximum frequency is at most ceil(n/2), since any more copies of one character than that would force two of them to be adjacent no matter how the rest are arranged. This reduces the whole question to one counting pass and one comparison, with no need to actually construct or simulate any arrangement. Time: O(n) Space: O(1)

Count the frequency of each of the 26 letters and load them into a max-heap keyed by remaining count. Repeatedly pop the most frequent character that isn't the same as the last one placed, append it to a result buffer, decrement its count, and push it back if any remain (using a small holding slot for the just-placed character so it isn't picked again immediately); answer "Yes" if this greedy construction manages to place all n characters, "No" if it ever gets stuck. This actually constructs a valid arrangement (proving feasibility constructively) rather than searching permutations, but does more work than strictly necessary just to answer a yes/no question. Time: O(n log 26) Space: O(1)

Generate permutations of the string's characters (or recursively try placing each remaining character at each position) and, for each candidate arrangement, scan it left to right to check whether any two adjacent characters are equal; stop and print "Yes" the moment a valid arrangement is found, or "No" if every permutation is exhausted without one. This directly matches the problem's wording ("can the characters be rearranged...") but the number of distinct permutations is factorial in the string length, making it usable only for tiny strings. Time: O(n!) Space: O(n)

1. Count the frequency of every character. 2. A valid rearrangement exists if and only if the HIGHEST frequency is at most ceil(n/2), where n is the string's total length. 3. This single feasibility check answers the question directly - no actual rearrangement needs to be constructed since only Yes/No is asked.

Time: O(n) - one pass to count character frequencies, plus a fixed 26-step check for the maximum. Space: O(1) - a fixed-size (26-slot) frequency array, regardless of the input string's length.

a string of length 1 (always 'Yes'), a string where one character's frequency exceeds ceil(n/2) (answer 'No'), and |s| at its maximum of 10^5 to confirm the frequency-count check runs efficiently.

Be ready to briefly justify WHY the ceil(n/2) bound is exactly the tipping point - if one character's count exceeds this, there simply aren't enough OTHER characters to separate all of its occurrences, no matter how cleverly arranged.