Is Rearrange String to Avoid Character Pair easy or hard?

The problem is generally classified as Easy when constraints are small or only basic adjacency rules exist. The heap-based optimization moves it closer to Medium interview difficulty because it requires careful greedy reasoning.

Rearrange String to Avoid Character Pair Python/Java solution

Python solutions usually use collections.Counter with heapq, while Java implementations commonly use HashMap and PriorityQueue. Both approaches achieve O(n log k) time complexity with clean greedy logic.

How to solve Rearrange String to Avoid Character Pair in O(n)?

An O(n) solution is possible when the character range is fixed and small, such as lowercase English letters. You can use frequency arrays and direct placement instead of a heap. For the general case with arbitrary characters, O(n log k) is the standard optimal complexity.

What is the best approach for Rearrange String to Avoid Character Pair?

The max heap greedy approach is usually the best solution because it always selects the most frequent valid character while avoiding restricted adjacent pairs. It runs in O(n log k) time, where k is the number of unique characters, and uses O(k) extra space.

Is Rearrange String to Avoid Character Pair asked at Google/Amazon/Meta?

String rearrangement and greedy scheduling problems are common in interviews at Google, Amazon, Meta, and other large tech companies. Variants often test heap usage, frequency counting, and adjacency constraints under time pressure.

What data structure is used in Rearrange String to Avoid Character Pair?

Most efficient solutions use a hash map for frequency counting and a max heap or priority queue for selecting the next valid character. Arrays can replace hash maps when the character set is fixed.

What is the time complexity of Rearrange String to Avoid Character Pair?

The optimal solution typically runs in O(n log k) time using a priority queue or heap. Frequency counting takes O(n), and each heap insertion or removal costs O(log k). Space complexity is O(k).

Description Hints 3 Solution Video 6:04

3992. Rearrange String to Avoid Character Pair

Easy77.8% acceptance

You are given a string s and two distinct lowercase English letters x and y.

Rearrange the characters of s to construct a new string t such that:

t is a permutation of s.
Every occurrence of y appears before every occurrence of x in t.

Return any valid string t.

Example 1:

Input: s = "aabc", x = "a", y = "c"

Output: "cbaa"

Explanation:

The string "cbaa" is a permutation of "aabc", and every occurrence of 'c' appears before every occurrence of 'a'.

Example 2:

Input: s = "dcab", x = "d", y = "b"

Output: "cabd"

Explanation:

The string "cabd" is a permutation of "dcab", and every occurrence of 'b' appears before every occurrence of 'd'.

Example 3:

Input: s = "axe", x = "o", y = "x"

Output: "axe"

Explanation:

The string "axe" is already valid. Since 'o' does not occur in the string, the required condition is automatically satisfied.

Constraints:

1 <= s.length <= 100
s consists of lowercase English letters.
x and y are lowercase English letters.
x != y

Topics

Hints open one at a time

Hint 1

Only the relative order between occurrences of x and y matters.

Hint 2

One approach is to place all occurrences of y before all other characters, and place all occurrences of x after them.

Hint 3

Another approach is to sort the characters of s. If x < y, sort in descending order; otherwise, sort in ascending order.

After sorting this way, every occurrence of y will appear before every occurrence of x.

6:04

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def rearrangeString(self, s: str, x: str, y: str) -> str:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

"aabc"
"a"
"c"

Input

"dcab"
"d"
"b"

Input

"axe"
"o"
"x"

Your code is saved on this device.Solution