767. Reorganize String

Reorganize String (LeetCode 767) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Heap (Priority Queue) Patterns pattern, in the Scheduling / Minimum Cost (Greedy with Priority Queue) subpattern.

• NeetCode 250 · #118 of 250 · Heap / Priority Queue

How to solve Reorganize String

Reorganize String is a Scheduling and Minimum Cost problem, part of Heap (Priority Queue) Patterns. Solve scheduling and optimization problems using priority queue with greedy approach.

Work towards the solution in these steps:

1. Alternate placing the most common letters.

The reference solution runs in O(nloga) time and O(a) space.

The Reorganize String solution and editorial walks through the full approach with reference code.

Problem statement

Given a string s, rearrange the characters of s so that any two adjacent characters are not the same.

Return any possible rearrangement of s or return "" if not possible.

Example 1:

Input: s = "aab" Output: "aba"

Example 2:

Input: s = "aaab" Output: ""

Constraints:

- 1 <= s.length <= 500

- s consists of lowercase English letters.

Topics and companies

Topics: Hash Table, String, Greedy, Sorting, Heap (Priority Queue), Counting.

Reported in interviews at Amazon, Google, Facebook, Microsoft, Wish, Uber, Goldman Sachs.

How to practise Reorganize String on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(nloga) time and O(a) space.

Open Reorganize String in the code editor, or read the Reorganize String editorial for a worked solution with its approach and complexity analysis.

Where Reorganize String sits in the DSA pattern sheet

• Heap (Priority Queue) Patterns pattern guide
• Scheduling / Minimum Cost (Greedy with Priority Queue) subpattern
• The full DSA patterns sheet

Problems related to Reorganize String

Other problems that use the same Scheduling / Minimum Cost (Greedy with Priority Queue) and Heap (Priority Queue) Patterns techniques:

• Furthest Building You Can Reach — Medium, same subpattern
• IPO — Hard, same subpattern
• Longest Happy String — Medium, same subpattern
• Maximum Average Pass Ratio — Medium, same subpattern
• Meeting Rooms II — Medium, same subpattern
• Meeting Rooms III — Hard, same subpattern

Reorganize String FAQ