Skip to content

Latest commit

 

History

History
163 lines (146 loc) · 5.61 KB

README.md

File metadata and controls

163 lines (146 loc) · 5.61 KB

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.

Companies: Amazon, Pinterest, Google

Related Topics:
Hash Table, String, Greedy, Sorting, Heap (Priority Queue), Counting

Similar Questions:

Solution 1. Sequential Placing (Greedy)

We place the letters from left to right. We always pick the letter that has the maximum count and is not the previously placed letter.

// OJ: https://leetcode.com/problems/reorganize-string/
// Author: github.com/lzl124631x
// Time: O(NA) where A is the size of the alphabet
// Space: O(A)
class Solution {
public:
    string reorganizeString(string s) {
        int cnt[26] = {}, mxCnt = 0;
        for (char c : s) mxCnt = max(mxCnt, ++cnt[c - 'a']);
        if (mxCnt > (s.size() + 1) / 2) return "";
        string ans;
        for (int i = 0; i < s.size(); ++i) {
            int mxIndex = -1;
            for (int c = 0; c < 26; ++c) {
                if (cnt[c] == 0 || (ans.size() && ans.back() == 'a' + c) || (mxIndex != -1 && cnt[c] <= cnt[mxIndex])) continue;
                mxIndex = c;
            }
            cnt[mxIndex]--;
            ans.push_back('a' + mxIndex);
        }
        return ans;
    }
};

Solution 2. Sequential Placing (Greedy + Heap)

Similar to solution 1, but instead of traversing all the letters, we use a priority queue to pick the one with the maximum count.

Since we can't place the letter we just placed again, we store the letter we just placed in a temp variable prev, and push it back into the priority queue one round later.

// OJ: https://leetcode.com/problems/reorganize-string/
// Author: github.com/lzl124631x
// Time: O(A + NlogA) where A is the size of the alphabet
// Space: O(A)
class Solution {
public:
    string reorganizeString(string S) {
        int cnt[26] = {}, prev = -1;
        for (char c : S) cnt[c - 'a']++;
        auto cmp = [&](int a, int b) { return cnt[a] < cnt[b]; };
        priority_queue<int, vector<int>, decltype(cmp)> q(cmp);
        for (int i = 0; i < 26; ++i) if (cnt[i]) q.push(i);
        string ans;
        while (q.size()) {
            int c = q.top();
            q.pop();
            ans.push_back('a' + c);
            if (prev != -1) q.push(prev);
            if (--cnt[c]) prev = c;
            else prev = -1;
        }
        if (prev != -1) return "";
        return ans;
    }
};

Solution 3. Interleaving Placement

We fill the even indices first, then the odd indices.

// OJ: https://leetcode.com/problems/reorganize-string/
// Author: github.com/lzl124631x
// Time: O(AlogA + N) where A is the size of the alphabet 
// Space: O(A)
// Ref: https://leetcode.com/problems/reorganize-string/solution/
class Solution {
public:
    string reorganizeString(string s) {
        int N = s.size(), cnt[26] = {}, j = 0;
        for (char c : s) cnt[c - 'a'] += 100;
        for (int i = 0; i < 26; ++i) cnt[i] += i;
        sort(begin(cnt), end(cnt), greater<>());
        string ans(N, 0);
        for (int n : cnt) {
            int ct = n / 100, ch = n % 100;
            if (ct == 0) continue;
            if (ct > (N + 1) / 2) return "";
            while (ct--) {
                ans[j] = ch + 'a';
                j = (j + 2) % N;
                if (j == 0) j = 1;
            }
        }
        return ans;
    }
};

We don't even need to sort the cnt array. We just need to place the letter with the maximum count first, and then place the rest in any order.

// OJ: https://leetcode.com/problems/reorganize-string
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(A)
class Solution {
public:
    string reorganizeString(string s) {
        int cnt[26] = {}, mxIndex = -1, N = s.size(), j = 0;
        for (char c : s) ++cnt[c - 'a'];
        for (int i = 0; i < 26; ++i) {
            if (mxIndex == -1 || cnt[i] > cnt[mxIndex]) mxIndex = i;
        }
        if (cnt[mxIndex] > (N + 1) / 2) return "";
        string ans(N, 0);
        // Place the most frequent letter
        while (cnt[mxIndex]--) {
            ans[j] = 'a' + mxIndex;
            j += 2;
        }
        // Place rest of the letters in any order
        for (int i = 0; i < 26; ++i) {
            while (cnt[i]-- > 0) {
                if (j >= N) j = 1;
                ans[j] = 'a' + i;
                j += 2;
            }
        }
        return ans;
    }
};