algoadvance

Leetcode 767. Reorganize String

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 an empty string if no such rearrangement is possible.

Example 1

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

Example 2

Input: s = "aaab" Output: ""

Clarifying Questions

  1. What should be returned if it is impossible to rearrange the string to meet the requirement?
    • You should return an empty string "".
  2. Are all characters in the string lowercase English letters?
    • Yes, the problem can assume that all characters are lowercase English letters (a-z).
  3. What is the maximum length of the input string?
    • The maximum length of s is 500.

Strategy

  1. Count Character Frequencies:
    • Use a hash map (or an array of size 26) to count the frequency of each character.
  2. Max Heap for Frequency:
    • Use a max heap (priority queue) to keep track of characters by their frequencies. The most frequent characters should be at the top.
  3. Rebuild the String:
    • Repeatedly pull two most frequent characters from the heap and add them to the output string. This ensures that no two adjacent characters are the same.
    • After adding characters to the result, decrease their frequency and if they still have a remaining count, push them back into the heap.
  4. Check for Possibility:
    • If at any moment the count of a character (while constructing the result) becomes more than half the size of the remaining characters + 1, then it is impossible to rearrange.

Code

import java.util.PriorityQueue;

public class Solution {
    public String reorganizeString(String s) {
        // Character frequency array
        int[] freq = new int[26];
        for (char c : s.toCharArray()) {
            freq[c - 'a']++;
        }
        
        // Max Heap
        PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> b[1] - a[1]);
        for (int i = 0; i < 26; i++) {
            if (freq[i] > 0) {
                if (freq[i] > (s.length() + 1) / 2) {
                    return ""; // Not possible to rearrange
                }
                maxHeap.add(new int[]{i, freq[i]});
            }
        }
        
        StringBuilder result = new StringBuilder();
        
        // Reorganize the string
        while (maxHeap.size() >= 2) {
            int[] first = maxHeap.poll();
            int[] second = maxHeap.poll();
            
            // Append characters to the result
            result.append((char)(first[0] + 'a'));
            result.append((char)(second[0] + 'a'));
            
            // Decrease frequency and push back into heap if still remaining
            if (--first[1] > 0) maxHeap.add(first);
            if (--second[1] > 0) maxHeap.add(second);
        }
        
        // If one character left in heap
        if (!maxHeap.isEmpty()) {
            int[] last = maxHeap.poll();
            if (last[1] > 1) {
                return ""; // Not possible to rearrange
            }
            result.append((char)(last[0] + 'a'));
        }
        
        return result.toString();
    }
}

Time Complexity

  1. Counting Frequencies:
    • This takes O(n), where n is the length of the string.
  2. Building the Max Heap:
    • We have up to 26 characters, so inserting into and extracting from the max heap operates in O(log 26) which is constant.
  3. Reconstructing the String:
    • This takes O(n) as we build the final string.

Therefore, the overall time complexity is O(n), mostly dominated by the initial counting and the final string reconstruction steps.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI