LeetCode 767: Reorganize String

Question

Here I'm posting my code for the Reorganize String problem on LeetCode. If you have time and would like to review, please do so, I'd appreciate that.

On LeetCode, we are only allowed to change the argument names and brute force algorithms are discouraged, usually fail with TLE (Time Limit Error) or MLE (Memory Limit Error).

Problem

Given a string S, check if the letters can be rearranged so that two characters that are adjacent to each other are not the same.

If possible, output any possible result. If not possible, return the empty string.

Example 1:

Input: S = "aab" Output: "aba" Example 2:

Input: S = "aaab" Output: "" Note:

S will consist of lowercase letters and have length in range [1, 500].

Java

class Solution {
 public String reorganizeString(String baseString) {
 int[] charMap = initializeCharMap26(baseString);
 int max = 0;
 int letter = 0;
 for (int iter = 0; iter < charMap.length; iter++)
 if (charMap[iter] > max) {
 max = charMap[iter];
 letter = iter;
 }
 if (max > ((-~baseString.length()) >> 1))
 return "";
 char[] reorganized = new char[baseString.length()];
 int index = 0;
 while (charMap[letter] > 0) {
 reorganized[index] = (char) (letter + 97);
 index += 2;
 charMap[letter]--;
 }
 for (int iter = 0; iter < charMap.length; iter++) {
 while (charMap[iter] > 0) {
 if (index >= reorganized.length)
 index = 1;
 reorganized[index] = (char) (iter + 97);
 index += 2;
 charMap[iter]--;
 }
 }
 return String.valueOf(reorganized);
 }
 private int[] initializeCharMap26(String baseString) {
 int[] charMap = new int[26];
 for (int i = 0; i < baseString.length(); i++)
 charMap[baseString.charAt(i) - 97]++;
 return charMap;
 }
}

Reference

767. Reorganize String (Problem)

767. Reorganize String (Solution)

Answer 1

Nice work! It's an efficient solution (linear in the length of the input string), using a simple yet quite clever logic to reorganize the letters, reasonably easy to read and well-formatted.

Improving readability

It's good to extract logical steps to helper methods, as you did for initializeCharMap26. You could split reorganizeString a bit further, extracting the logic of creating the reorganized string from parameters: the count of letters, the most common letter, and the target length.

Instead of the hardcoded 97, you could use 'a'. That explains it better where the magic number comes from, and it's also easier to remember. To make the code even easier to understand, and to eliminate some duplicate logic, it would be good to create helper functions charToIndex and indexToChar.

I think this part is cryptic and difficult to understand:

if (max > ((-~baseString.length()) >> 1))
 return "";

The idea is that given the count of the most frequent character, if there are not enough other characters, then the string cannot be reorganized. That is, if the length of the string is n, the most frequent character happens k times, then there must be at least k - 1 other characters. In other words, n - k >= k - 1 must hold. If we rewrite the condition to reflect this logic, I think it will be easier to understand:

if (baseString.length() - max < max - 1)
 return "";

Using better names

I think some of the names could be better to be more descriptive, for example:

• charMap -> charCounts
• letter -> mostFrequentLetter
• max -> mostFrequentLetterCount
• initializeCharMap26 -> stringToCharCounts, or even just toCharCounts

I'm used to seeing iter (or it) when iterating of the values of an iterable, and i or index in simple counting loops iterating over array indexes.