Daily LeetCode Problems: Problem 767. Reorganize String

Unlocking String Reorganization: Crafting Non-Adjacent Char Sequences

Introduction:

Welcome to another insightful problem-solving article! In this edition, we’ll delve into problem 767 from LeetCode: “Reorganize String”. This problem revolves around reorganizing a given string such that no two adjacent characters are the same. We’ll explore the problem statement, devise a reorganization strategy, analyze complexity, and provide a step-by-step solution.

Problem Statement:

Given a string s, our goal is to rearrange its characters in a way that no two adjacent characters are the same. If such reorganization is possible, we’ll return any valid rearrangement. If it’s not possible, we’ll return an empty string.

Approach:

To solve this problem efficiently, we’ll consider the frequency of each character in the string. We’ll arrange the characters in a way that the most frequent characters are separated by less frequent characters.

Pseudocode:

def reorganizeString(s: str) -> str:
    counter = collections.Counter(s)
    max_heap = [(-freq, char) for char, freq in counter.items()]
    heapq.heapify(max_heap)
    
    result = []
    while len(max_heap) >= 2:
        freq1, char1 = heapq.heappop(max_heap)
        freq2, char2 = heapq.heappop(max_heap)
        
        result.extend([char1, char2])
        if freq1 + 1 < 0:
            heapq.heappush(max_heap, (freq1 + 1, char1))
        if freq2 + 1 < 0:
            heapq.heappush(max_heap, (freq2 + 1, char2))
    
    if max_heap:
        freq, char = heapq.heappop(max_heap)
        if freq < -1:
            return ""
        result.append(char)
    
    return "".join(result)

Complexity Analysis:

Let’s analyze the complexity of our solution:

• Time complexity: We iterate through the characters and perform heap operations, resulting in a time complexity of O(n * log(k)), where n is the length of the string and k is the number of unique characters.
• Space complexity: We use additional space for the counter and max heap, resulting in a space complexity of O(k).

Step-by-Step Solution:

1. Create a counter to calculate the frequency of each character in the string.
2. Create a max heap with negative frequencies and characters as tuples.
3. While there are at least two characters in the max heap:

• Pop two characters with the highest frequencies from the max heap.
• Append these characters to the result list.
• If their frequencies are not exhausted, push them back with decremented frequencies.

1. If there’s a character left in the max heap:

• If its frequency is less than -1, it’s not possible to rearrange, so return an empty string.
• Otherwise, append the character to the result list.

1. Return the result list as a string.

Full Solution

Python

class Solution:
  def reorganizeString(self, s: str) -> str:
    count = collections.Counter(s)
    if max(count.values()) > (len(s) + 1) // 2:
      return ''

    ans = []
    maxHeap = [(-freq, c) for c, freq in count.items()]
    heapq.heapify(maxHeap)
    prevFreq = 0
    prevChar = '@'

    while maxHeap:
      # Get the most freq letter.
      freq, c = heapq.heappop(maxHeap)
      ans.append(c)
      # Add the previous letter back so that any two adjacent characters are not
      # the same.
      if prevFreq < 0:
        heapq.heappush(maxHeap, (prevFreq, prevChar))
      prevFreq = freq + 1
      prevChar = c

    return ''.join(ans)

Java

public class Solution {
  public String reorganizeString(String s) {
    Map<Character, Integer> count = new HashMap<>();
    int maxFreq = 0;

    for (final char c : s.toCharArray())
      maxFreq = Math.max(maxFreq, count.merge(c, 1, Integer::sum));

    if (maxFreq > (s.length() + 1) / 2)
      return "";

    StringBuilder sb = new StringBuilder();
    // (freq, c)
    Queue<Pair<Integer, Character>> maxHeap =
        new PriorityQueue<>((a, b) -> b.getKey() - a.getKey());
    int prevFreq = 0;
    char prevChar = '@';

    for (final char c : count.keySet())
      maxHeap.offer(new Pair<>(count.get(c), c));

    while (!maxHeap.isEmpty()) {
      // Get the most freq letter.
      final int freq = maxHeap.peek().getKey();
      final char c = maxHeap.poll().getValue();
      sb.append(c);
      // Add the previous letter back so that any two adjacent characters are
      // not the same.
      if (prevFreq > 0)
        maxHeap.offer(new Pair<>(prevFreq, prevChar));
      prevFreq = freq - 1;
      prevChar = c;
    }

    return sb.toString();
  }
}

C++

class Solution {
 public:
  string reorganizeString(string s) {
    unordered_map<char, int> count;
    int maxFreq = 0;

    for (const char c : s)
      maxFreq = max(maxFreq, ++count[c]);

    if (maxFreq > (s.length() + 1) / 2)
      return "";

    string ans;
    priority_queue<pair<int, char>> maxHeap;  // (freq, c)
    int prevFreq = 0;
    char prevChar = '@';

    for (const auto& [c, freq] : count)
      maxHeap.emplace(freq, c);

    while (!maxHeap.empty()) {
      // Get the most freq letter.
      const auto [freq, c] = maxHeap.top();
      maxHeap.pop();
      ans += c;
      // Add the previous letter back so that any two adjacent characters are
      // not the same.
      if (prevFreq > 0)
        maxHeap.emplace(prevFreq, prevChar);
      prevFreq = freq - 1;
      prevChar = c;
    }

    return ans;
  }
};

Conclusion:

In this article, we tackled problem 767, “Reorganize String,” by devising a strategy to rearrange characters in the string while ensuring that no two adjacent characters are the same. By considering character frequencies and utilizing a max heap, we were able to craft valid rearrangements. Understanding the problem statement and implementing our approach will allow you to skillfully reorganize strings to meet the given criteria. Happy string reorganization!