767. Reorganize String - cocoder39/coco39_LC GitHub Wiki

767. Reorganize String

step 1: inserting max_count_letter to s[0], s[2], s[4]...s[i] step 2: inserting the rest to s[i+2], s[i+4]... once reaches s[n-1] then restart from s[1]

class Solution:
    def reorganizeString(self, s: str) -> str:
        counters = collections.Counter(s)
        max_count = 0
        max_count_letter = ''
        for letter in counters:
            if counters[letter] > max_count:
                max_count = counters[letter]
                max_count_letter = letter
        
        if max_count > (len(s) + 1) // 2:
            return ''
        
        res = [''] * len(s)
        i = 0
        while counters[max_count_letter] > 0:
            res[i] = max_count_letter
            i += 2
            counters[max_count_letter] -= 1
            
        for letter in counters:
            for j in range(counters[letter]):
                if i >= len(s):
                    i = 1
                    
                res[i] = letter
                i += 2
                
        return ''.join(res)

358. Rearrange String k Distance Apart is a general case of this problem.

class Solution:
    def reorganizeString(self, S: str) -> 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 + 2
            counters[next_candidate] -= 1
            if counters[next_candidate] == 0:
                del counters[next_candidate]
                del min_next_index[next_candidate]
        
        return ''.join(res)