Reorganize String

MEDIUM

Description

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.

Approaches

Checkout 3 different approaches to solve Reorganize String. Click on different approaches to view the approach and algorithm in detail.

Brute Force with Permutations

This approach generates all possible unique permutations of the input string and checks each one to see if it meets the condition that no two adjacent characters are the same. The first valid permutation found is returned. If no such permutation exists after checking all possibilities, it means a reorganization is not possible.

Algorithm

This approach is not implemented due to its extreme inefficiency. The general algorithm would be:
1. Define a recursive function, say generatePermutations, that explores all possible orderings of the characters in s.
1. To handle duplicate characters, use a frequency map of characters rather than swapping elements in an array to generate unique permutations.
1. In the recursive function, at each step, try to append every available character (from the frequency map) to the current permutation string.
1. Before appending, check if the character is the same as the last character added. If it is, skip this choice.
1. Once a permutation of length n is formed, it is a valid solution. Return it.
1. If the recursion completes without finding a solution, it's impossible.

The brute-force method involves exploring every single arrangement of the characters in the string s. This can be achieved using a backtracking algorithm. We would try to build a valid string character by character. At each position, we would try to place an available character, ensuring it's not the same as the character at the previous position. If we successfully build a string of the same length as s, we have found a solution. If we explore all possibilities and fail to do so, no solution exists. Due to the massive number of permutations (n!), this approach is computationally infeasible for the given constraints.

Complexity Analysis

Time Complexity: O(n! * n), where n is the length of the string. In the worst case, we might generate up to n! unique permutations, and for each, we might perform operations proportional to n. This is not a practical solution.Space Complexity: O(n), where n is the length of the string. This space is used for the recursion stack and to store the state of the permutation being built.

Pros and Cons

Pros:

Conceptually simple to understand.

Cons:

Extremely inefficient due to factorial time complexity.
Will time out for all but the smallest input strings (e.g., n > 10).

Code Solutions

Checking out 3 solutions in different languages for Reorganize String. Click on different languages to view the code.

class Solution {
public
  String reorganizeString(String s) {
    int[] cnt = new int[26];
    int mx = 0;
    for (char c : s.toCharArray()) {
      int t = c - 'a';
      ++cnt[t];
      mx = Math.max(mx, cnt[t]);
    }
    int n = s.length();
    if (mx > (n + 1) / 2) {
      return "";
    }
    int k = 0;
    for (int v : cnt) {
      if (v > 0) {
        ++k;
      }
    }
    int[][] m = new int[k][2];
    k = 0;
    for (int i = 0; i < 26; ++i) {
      if (cnt[i] > 0) {
        m[k++] = new int[]{cnt[i], i};
      }
    }
    Arrays.sort(m, (a, b)->b[0] - a[0]);
    k = 0;
    StringBuilder ans = new StringBuilder(s);
    for (int[] e : m) {
      int v = e[0], i = e[1];
      while (v-- > 0) {
        ans.setCharAt(k, (char)('a' + i));
        k += 2;
        if (k >= n) {
          k = 1;
        }
      }
    }
    return ans.toString();
  }
}

Video Solution

Watch the video walkthrough for Reorganize String

Algorithms:

Sorting

Patterns:

GreedyCounting

Data Structures:

Hash TableStringHeap (Priority Queue)

Companies:

Intuit |PayPal |Roblox |Walmart Labs |