767. Reorganize String

MediumGreedyHash TableStringCountingSortingHeap (Priority Queue)
Leetcode Link

Problem Description

The problem states that we have a string s, and we need to rearrange its characters so that no two adjacent characters are the same. If it's possible to arrange the string to satisfy this condition, we should return any one of the valid rearrangements. If it is not possible, we should return an empty string "".

Intuition

The key insight to solve this problem stems from the observation that if a character appears more than half of the string's length (rounded up), it is impossible to rearrange the string so that no two adjacent characters are the same, because there would be insufficient gaps between instances of this character to place other characters.

Considering this, we can use a greedy approach with the following logic:

  1. Count Frequencies: Count how many times each character appears in the given string. This will help us identify the most frequent characters which potentially could be a problem if they exceed the allowed limit.

  2. Check for Impossible Cases: If the most frequent character occurs more than half the length of the string (rounded up), then it is impossible to rearrange the string in the required manner. In such a case, we immediately return an empty string.

  3. Construct the Solution: If we can rearrange the string, we then fill the even indexes first (0, 2, 4 ...) with the most frequent characters. This ensures these characters are separated. If we reach the end of the string (going beyond the last index) in this process, we switch to the odd indexes (1, 3, 5 ...).

  4. Building the Output String: Starting with the most common character, fill the stringโ€™s indices as described. After placing all instances of the most common character, move to the next most common, and so forth, until the string is completely filled.

This algorithm efficiently ensures that for every character placed, it will not be adjacent to the same character, fulfilling the given problem constraint.

Learn more about Greedy, Sorting and Heap (Priority Queue) patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

Solution Approach

The Reference Solution Approach uses a hashmap and a sorting technique to tackle the problem. The detailed steps of implementing the solution are as follows:

  1. Using a Counter: The Counter class from Python's collections module is utilized to count occurrences of each character in the string. This creates a hashmap (a dictionary in Python) where keys are the characters and values are their counts.

  2. Determining the Maximum Frequency Character: By finding the maximum value in the Counter, we determine if there is a character that appears more often than (n + 1) // 2 times (n being the length of the string). If such a character exists, we return an empty string '' since it's impossible to rearrange the string per the problem's condition.

  3. Creating the Answer Array: An array ans is initialized having the same length as the string s. This will contain the rearranged characters and initially filled with None.

  4. Sorting by Frequency and Populating the Answer Array: Using most_common() on the Counter object, we retrieve characters and their counts sorted by frequency in descending order. We then iterate over these key-value pairs.

  5. Placing Characters at Even Indices First: We start filling the ans array at index 'i' initialized to 0, which targets even indices. For each character k, we decrement its count v by 1 each time it's placed in the array, and increment i by 2 to move to the next even index.

  6. Switching to Odd Indices: If i becomes equal to or greater than n, it means we've run out of even indices. Thus, we reset i to 1 to start filling odd indices.

  7. Building the Final String: When the loop ends, all characters are distributed in the ans array in a way where no two identical characters are adjacent. We use ''.join(ans) to convert the array back into a string and return that as our solution.

These steps ensure that the solution is both efficient and satisfies the problem's constraints, resulting in either a valid string rearrangement or an empty string if it's not possible.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

How many times is a tree node visited in a depth first search?

Example Walkthrough

Let's walk through a small example to illustrate the solution approach:

Suppose we are given the string s = "aabbcc". The string is 6 characters long, so no character should appear more than 6 / 2 = 3 times for us to be able to rearrange the characters as required.

Here's how we would apply our solution approach to this example:

  1. Using a Counter: We utilize the Counter class to get the count of each character in the string s. The result will be a hashmap like this: {'a': 2, 'b': 2, 'c': 2}.

  2. Determining the Maximum Frequency Character: The maximum count in our example is 2, which does not exceed 6 / 2 = 3. This means it's possible to rearrange the string, so we don't need to return an empty string "".

  3. Creating the Answer Array: We initialize an array ans of length 6 (since the string s has 6 characters), filled with None: [None, None, None, None, None, None].

  4. Sorting by Frequency and Populating the Answer Array: We sort the characters by their frequency. In our case, the counts are equal, but we proceeded with the available order: ['a', 'b', 'c'].

  5. Placing Characters at Even Indices First: Starting with a which has a count of 2, we place 'a' at index 0 and index 2: [a, None, a, None, None, None].

  6. Switching to Odd Indices: After we fill the even indices with a, we move to b and place it at indices 4 and then 1 because index 4 is still even and available: [a, b, a, None, b, None].

  7. Continuing the Pattern: Now we place c at the remaining indices, index 5 (which is the last even index) and then index 3: [a, b, a, c, b, c].

  8. Building the Final String: The ans array is now [a, b, a, c, b, c], and no two identical characters are adjacent. Finally, we join the array into a string to get our result: 'abacbc'.

Hence, the output is a valid rearrangement of the string s where no two adjacent characters are the same, demonstrating the effectiveness of the solution approach.

Solution Implementation

1from collections import Counter
2
3class Solution:
4    def reorganizeString(self, s: str) -> str:
5        # Calculate the length of the string
6        string_length = len(s)
7      
8        # Count the frequency of each character in the string
9        char_count = Counter(s)
10      
11        # Find the maximum frequency of any character
12        max_freq = max(char_count.values())
13      
14        # If the max frequency is more than half of the string length, round up,
15        # then the task is impossible as that character would need to be adjacent to itself.
16        if max_freq > (string_length + 1) // 2:
17            return ''
18      
19        # Initialize index for placing characters
20        index = 0
21      
22        # Create a list to store the reorganized string
23        reorganized = [None] * string_length
24      
25        # Fill in the characters, starting with the most common
26        for char, freq in char_count.most_common():
27            while freq:
28                # Place the character at the current index
29                reorganized[index] = char
30                # Decrease the frequency count
31                freq -= 1
32                # Move to the next even index or the first odd index if the end is reached
33                index += 2
34                if index >= string_length:
35                    index = 1
36      
37        # Return the list as a string
38        return ''.join(reorganized)
39
1class Solution {
2    public String reorganizeString(String s) {
3        // Array to count the frequency of each character.
4        int[] charCount = new int[26];
5        int maxCount = 0; // Keep track of the maximum character frequency
6      
7        // Count the frequency of each character in the string.
8        for (char character : s.toCharArray()) {
9            int index = character - 'a';
10            charCount[index]++;
11            // Update maxCount if current character's frequency is higher.
12            maxCount = Math.max(maxCount, charCount[index]);
13        }
14      
15        int length = s.length();
16        // If the most frequent character is more than half of the length of the string,
17        // it is impossible to reorganize.
18        if (maxCount > (length + 1) / 2) {
19            return "";
20        }
21      
22        int distinctChars = 0;
23        // Count the number of distinct characters.
24        for (int count : charCount) {
25            if (count > 0) {
26                distinctChars++;
27            }
28        }
29      
30        // Create a matrix to store frequency and index of each character.
31        int[][] charFrequency = new int[distinctChars][2];
32        distinctChars = 0;
33        for (int i = 0; i < 26; ++i) {
34            if (charCount[i] > 0) {
35                charFrequency[distinctChars++] = new int[] {charCount[i], i};
36            }
37        }
38      
39        // Sort the character frequency matrix by frequency in descending order.
40        Arrays.sort(charFrequency, (a, b) -> b[0] - a[0]);
41      
42        // StringBuilder to build the result.
43        StringBuilder result = new StringBuilder(s);
44        int idx = 0; // Index used for inserting characters in result.
45      
46        // Fill the characters in the result string.
47        for (int[] entry : charFrequency) {
48            int freq = entry[0], charIndex = entry[1];
49            while (freq-- > 0) {
50                result.setCharAt(idx, (char) ('a' + charIndex));
51                idx += 2;
52                // Wrap around if index goes beyond string length.
53                if (idx >= length) {
54                    idx = 1;
55                }
56            }
57        }
58      
59        return result.toString();
60    }
61}
62
1class Solution {
2public:
3    // Function to reorganize the string such that no two adjacent characters are the same
4    string reorganizeString(string s) {
5        vector<int> counts(26, 0); // Counts for each character in the alphabet
6        // Calculate the counts for each character in the string
7        for (char c : s) {
8            ++counts[c - 'a'];
9        }
10        // Find the maximum occurrence of a character
11        int maxCount = *max_element(counts.begin(), counts.end());
12        int n = s.size();
13        // If the maximum count is more than half the length of the string, reorganization is not possible
14        if (maxCount > (n + 1) / 2) return "";
15      
16        // Pairing count of characters with their corresponding alphabet index
17        vector<pair<int, int>> charCounts;
18        for (int i = 0; i < 26; ++i) {
19            if (counts[i]) {
20                charCounts.push_back({counts[i], i});
21            }
22        }
23        // Sort the character counts in ascending order
24        sort(charCounts.begin(), charCounts.end());
25        // Then reverse to have descending order
26        reverse(charCounts.begin(), charCounts.end());
27      
28        // Prepare the result string with the same length as the input
29        string result = s;
30        int idx = 0; // Index to keep track of placement in result string
31      
32        // Loop through sorted character counts and distribute characters across the result string
33        for (auto& entry : charCounts) {
34            int count = entry.first, alphabetIndex = entry.second;
35            while (count--) {
36                // Place the character at the index, then skip one place for the next character
37                result[idx] = 'a' + alphabetIndex;
38                idx += 2; // Move to the next position skipping one
39              
40                // If we reach or pass the end of the string, start placing characters at the first odd index
41                if (idx >= n) idx = 1;
42            }
43        }
44        // Return the reorganized string
45        return result;
46    }
47};
48
1// Function to reorganize the string so that no two adjacent characters are the same
2function reorganizeString(s: string): string {
3    const counts = new Array(26).fill(0); // Counts for each character in the alphabet
4    // Calculate the counts for each character in the string
5    for (let c of s) {
6        counts[c.charCodeAt(0) - 'a'.charCodeAt(0)]++;
7    }
8    // Find the maximum occurrence of a character
9    const maxCount = Math.max(...counts);
10    const n = s.length;
11    // If the maximum count is more than half the length of the string, reorganization is not possible
12    if (maxCount > Math.floor((n + 1) / 2)) return "";
13  
14    // Pairing count of characters with their corresponding alphabet index
15    const charCounts: [number, number][] = [];
16    for (let i = 0; i < 26; ++i) {
17        if (counts[i]) {
18            charCounts.push([counts[i], i]);
19        }
20    }
21    // Sort the character counts in descending order of frequency
22    charCounts.sort((a, b) => b[0] - a[0]);
23  
24    // Prepare the result string with the same length as the input
25    let result = s;
26    let idx = 0; // Index to keep track of placement in the result string
27  
28    // Loop through sorted character counts and distribute characters across the result string
29    for (let [count, alphabetIndex] of charCounts) {
30        while (count > 0) {
31            // Place the character at the index, then skip one place for the next character
32            result = setCharAt(result, idx, String.fromCharCode('a'.charCodeAt(0) + alphabetIndex));
33            idx += 2; // Move to the next position skipping one
34
35            // If we reach or pass the end of the string, start placing characters at the first odd index
36            if (idx >= n) idx = 1;
37            count--;
38        }
39    }
40    // Return the reorganized string
41    return result;
42}
43
44// Helper function to replace a character at a specific index in a string
45function setCharAt(str: string, index: number, ch: string): string {
46    if (index > str.length - 1) return str;
47    return str.substring(0, index) + ch + str.substring(index + 1);
48}
49
Not Sure What to Study? Take the 2-min Quiz๏ผš

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)

Time and Space Complexity

The time complexity of the code is O(n + n log n). The Counter(s) initialization takes O(n) time to count frequencies of each character in the input string of length n. The .most_common() method sorts these counts, which takes O(n log n) time in the worst case when all characters are different. The while loop inside the for loop iterates over all n characters to construct the output string, resulting in O(n) time. Therefore, the most expensive operation is the sorting with O(n log n) time, and when added to the other O(n) time operations, the overall time complexity remains O(n + n log n).

The space complexity of the code is O(n). The space complexity comes from storing the count of each character using Counter which requires O(n) space in the worst case where all characters are unique. Additionally, the ans array is used to build the output string and has a length of n, contributing O(n) space. However, since these do not scale with n together (the Counter won't scale to n if ans is n, and vice versa), the total space complexity is still O(n).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following is a good use case for backtracking?

Recommended Readings

Greedy Introduction

Greedy Introduction iframe width 560 height 315 src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you

Sorting Summary

Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced

Heap Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos heap svg Priority Queue and Heap What is the relationship between priority queue and heap Priority Queue is an Abstract Data Type and Heap is the concrete data structure we use to implement a priority queue Priority Queue A priority queue

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ