358. Rearrange String k Distance Apart - cocoder39/coco39_LC GitHub Wiki

358. Rearrange String k Distance Apart

Notes 2020:

How to get the best next candidate: Among all candidates that can be inserted into current position, pick the one with the highest count

class Solution:
    def rearrangeString(self, s: str, k: int) -> str:
        min_next_index = {ch: 0 for ch in s}
        counters = collections.Counter(s)

        def getNextCandidate(index):            
            next_candidate = None
            freq_next_candidate = 0
            for ch in counters:
                if index >= min_next_index[ch] and counters[ch] > freq_next_candidate:
                    next_candidate = ch
                    freq_next_candidate = counters[ch]
            return next_candidate
    
        res = []
        while len(res) < len(s):
            cur_idx = len(res)
            next_candidate = getNextCandidate(cur_idx)
            if not next_candidate:
                return ''
            
            res.append(next_candidate)
            min_next_index[next_candidate] = cur_idx + k
            counters[next_candidate] -= 1
            if counters[next_candidate] == 0:
                del counters[next_candidate]
                del min_next_index[next_candidate]
        
        return ''.join(res)

There are at most 26 distinct chars. T = O(N) where N is len(S). Space is O(1)

=================================================================================

the best next candidate char is the char with the max remaining count and is valid to be inserted into that position of res

time complexity is O(n) where n is the length of str

class Solution {
public:
    string rearrangeString(string str, int k) {
        vector<int> count(26);
        for (auto c : str) {
            count[c - 'a']++;
        }
        
        string res(str.length(), ' ');
        vector<int> lastIdx(26, INT_MIN);
        for (int i = 0; i < str.length(); i++) {
            int idx = helper(i, lastIdx, k, count);
            if (idx == -1)  return "";
            res[i] = 'a' + idx;
            count[idx]--;
            lastIdx[idx] = i;
        }
        return res;
    }
private:
    int helper(int idx, vector<int>& lastIdx, int k, vector<int>& count) {
        int res = -1, high = 0;
        for (int i = 0; i < 26; i++) {
            if (count[i] > high && idx >= lastIdx[i] + k) {
                res = i;
                high = count[i];
            }
        }
        return res;
    }
};

using multimap

string rearrangeString(string str, int k) {
        vector<int> count(26);
        for (auto c : str) {
            count[c - 'a']++;
        }
        
        multimap<int, char> mp;
        for (int i = 0; i < 26; i++) {
            if (count[i] > 0) {
                mp.insert({count[i], 'a' + i});
            }
        }
        
        string res(str.length(), ' ');
        vector<int> lastIdx(26, INT_MIN);
        for (int i = 0; i < str.length(); i++) {
            bool found = false;
            for (auto it = mp.rbegin(); it != mp.rend(); it++) {
                int cnt = it->first;
                char c = it->second;
                if (i >= lastIdx[c - 'a'] + k) {
                    found = true;
                    mp.erase(--it.base()); //one offset from reverse_iterator's base to corresponding iterator
                    lastIdx[c - 'a'] = i;
                    res[i] = c;
                    if (cnt > 1) {
                        mp.insert({cnt - 1, c});
                    } 
                    break;
                }
            }
            if (!found)    return "";
        }
        return res;
    }
⚠️ **GitHub.com Fallback** ⚠️