hard Rearrange String
Problem Statement
Given a string, find if its letters can be rearranged in such a way that no two same characters come next to each other.
Example 1:
Input: "aappp"
Output: "papap"
Explanation: In "papap", none of the repeating characters come next to each other.
Example 2:
Input: "Programming"
Output: "rgmrgmPiano" or "gmringmrPoa" or "gmrPagimnor", etc.
Explanation: None of the repeating characters come next to each other.
Example 3:
Input: "aapa"
Output: ""
Explanation: In all arrangements of "aapa", atleast two 'a' will come together e.g., "apaa", "paaa".
Constraints:
1 <= s.length <= 500sconsists of lowercase English letters.
Try it yourself
Try solving this question here:
✅ Solution Rearrange String
Problem Statement
Given a string, find if its letters can be rearranged in such a way that no two same characters come next to each other.
Example 1:
Input: "aappp"
Output: "papap"
Explanation: In "papap", none of the repeating characters come next to each other.
Example 2:
Input: "Programming"
Output: "rgmrgmPiano" or "gmringmrPoa" or "gmrPagimnor", etc.
Explanation: None of the repeating characters come next to each other.
Example 3:
Input: "aapa"
Output: ""
Explanation: In all arrangements of "aapa", atleast two 'a' will come together e.g., "apaa", "paaa".
Constraints:
1 <= s.length <= 500sconsists of lowercase English letters.
Solution
This problem follows the Top ‘K’ Numbers pattern. We can follow a greedy approach to find an arrangement of the given string where no two same characters come next to each other.
We can work in a stepwise fashion to create a string with all characters from the input string. Following a greedy approach, we should first append the most frequent characters to the output strings, for which we can use a Max Heap. By appending the most frequent character first, we have the best chance to find a string where no two same characters come next to each other.
So in each step, we should append one occurrence of the highest frequency character to the output string. We will not put this character back in the heap to ensure that no two same characters are adjacent to each other. In the next step, we should process the next most frequent character from the heap in the same way and then, at the end of this step, insert the character from the previous step back to the heap after decrementing its frequency.
Following this algorithm, if we can append all the characters from the input string to the output string, we would have successfully found an arrangement of the given string where no two same characters appeared adjacent to each other.
Code
Here is what our algorithm will look like:
import java.util.*;
class Solution {
public String rearrangeString(String str) {
Map<Character, Integer> charFrequencyMap = new HashMap<>();
for (char chr : str.toCharArray()) charFrequencyMap.put(
chr,
charFrequencyMap.getOrDefault(chr, 0) + 1
);
PriorityQueue<Map.Entry<Character, Integer>> maxHeap = new PriorityQueue<
Map.Entry<Character, Integer>
>((e1, e2) -> e2.getValue() - e1.getValue());
// add all characters to the max heap
maxHeap.addAll(charFrequencyMap.entrySet());
Map.Entry<Character, Integer> previousEntry = null;
StringBuilder resultString = new StringBuilder(str.length());
while (!maxHeap.isEmpty()) {
Map.Entry<Character, Integer> currentEntry = maxHeap.poll();
// add the previous entry back in the heap if its frequency is greater than zero
if (previousEntry != null && previousEntry.getValue() > 0) maxHeap.offer(
previousEntry
);
// append the current character to the result string and decrement its count
resultString.append(currentEntry.getKey());
currentEntry.setValue(currentEntry.getValue() - 1);
previousEntry = currentEntry;
}
// if we were successful in appending all the characters to the result string,
// return it
return resultString.length() == str.length() ? resultString.toString() : "";
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println("Rearranged string: " + sol.rearrangeString("aappp"));
System.out.println(
"Rearranged string: " + sol.rearrangeString("Programming")
);
System.out.println("Rearranged string: " + sol.rearrangeString("aapa"));
}
}
Time Complexity
The time complexity of the above algorithm is O(N∗logN) where ‘N’ is the number of characters in the input string.
Space Complexity
The space complexity will be O(N), as in the worst case, we need to store all the ‘N’ characters in the HashMap.
🤖 Don't fully get this? Learn it with Claude
Stuck on Rearrange String? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.
Progressively stronger hints — you still solve it.
I'm working on the problem **Rearrange String** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
See the technique, not just code.
Explain the optimal approach to **Rearrange String** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
Catch bugs, edge cases, sub-optimality.
I'll paste my solution to **Rearrange String**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
Lock in recognition with look-alikes.
Give me 2 problems that use the SAME underlying pattern as **Rearrange String**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.