767. 重构字符串

题目描述

输入字符串 s。把其中的字符重新排列，使得任意两个相邻位置上的字符都不相同。

如果可以做到，返回任意一种满足要求的排列；如果做不到，返回空字符串 ""。

示例 1

输入：s = "aab"
输出："aba"

解释：两个 a 被 b 隔开即可。

示例 2

输入：s = "aaab"
输出：""

解释：a 有 3 个而其他字符只有 1 个，无论怎样排都有两个 a 相邻。

数据范围

1 <= s.length <= 500
s 只含小写字母。

解题思路：贪心 + 大根堆

贪心：每一步都放“剩余次数最多、且不等于上一个字符”的字母。用最大堆按剩余次数取字母；刚放下的字母先不放回堆，而是存在 prev 里“冷却一轮”，下一轮取出新字母后再把 prev 放回堆。这样相邻两个字母一定不同。如果堆空了 prev 还有剩余，说明只剩这一种字母且和末尾相同，无解。

为什么正确

res 中相邻字符互不相同；prev 是 res 最后一个字符（如果它还有剩余），它暂时不在堆中。

复杂度分析

时间 O(n log k)，k 为字母种类（≤ 26）；空间 O(k)。

易错点

判断无解的条件也可以提前算：最多的字母次数超过 (n+1)/2 就无解。答案不唯一，只要相邻不同即可。别把刚取出的字母立刻放回堆，否则下一轮可能又取到它。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Solution:
    def reorganizeString(self, s: str) -> str:
        cnt = collections.Counter(s)
        heap = [(-c, ch) for ch, c in cnt.items()]
        heapq.heapify(heap)
        res = []
        prev = None
        while heap:
            c, ch = heapq.heappop(heap)
            res.append(ch)
            if prev:
                heapq.heappush(heap, prev)
            prev = (c + 1, ch) if c + 1 < 0 else None
        return '' if prev else ''.join(res)

class Solution {
    public String reorganizeString(String s) {
        int[] cnt = new int[26];
        for (char ch : s.toCharArray()) cnt[ch - 'a']++;
        PriorityQueue<int[]> heap = new PriorityQueue<>((x, y) -> x[0] != y[0] ? y[0] - x[0] : x[1] - y[1]);
        for (int i = 0; i < 26; i++) if (cnt[i] > 0) heap.offer(new int[]{cnt[i], i});
        StringBuilder res = new StringBuilder();
        int[] prev = null;
        while (!heap.isEmpty()) {
            int[] cur = heap.poll();
            res.append((char) ('a' + cur[1]));
            if (prev != null) {
                heap.offer(prev);
            }
            prev = cur[0] - 1 > 0 ? new int[]{cur[0] - 1, cur[1]} : null;
        }
        return prev != null ? "" : res.toString();
    }
}

class Solution {
public:
    string reorganizeString(string s) {
        int cnt[26] = {0};
        for (char ch : s) cnt[ch - 'a']++;
        priority_queue<pair<int, char>> heap;
        for (int i = 0; i < 26; i++) if (cnt[i]) heap.push({cnt[i], char('a' + i)});
        string res;
        pair<int, char> prev = {0, 0};
        while (!heap.empty()) {
            auto [c, ch] = heap.top();
            heap.pop();
            res += ch;
            if (prev.first > 0) {
                heap.push(prev);
            }
            prev = {c - 1, ch};
        }
        return prev.first > 0 ? "" : res;
    }
};

type item struct {
	c  int
	ch byte
}
type charHeap []item

func (h charHeap) Len() int { return len(h) }
func (h charHeap) Less(i, j int) bool {
	if h[i].c != h[j].c {
		return h[i].c > h[j].c
	}
	return h[i].ch < h[j].ch
}
func (h charHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *charHeap) Push(x any)   { *h = append(*h, x.(item)) }
func (h *charHeap) Pop() any {
	old := *h
	x := old[len(old)-1]
	*h = old[:len(old)-1]
	return x
}

func reorganizeString(s string) string {
	cnt := [26]int{}
	for i := 0; i < len(s); i++ {
		cnt[s[i]-'a']++
	}
	h := &charHeap{}
	for i := 0; i < 26; i++ {
		if cnt[i] > 0 {
			*h = append(*h, item{cnt[i], byte('a' + i)})
		}
	}
	heap.Init(h)
	res := []byte{}
	var prev *item
	for h.Len() > 0 {
		cur := heap.Pop(h).(item)
		res = append(res, cur.ch)
		if prev != nil {
			heap.Push(h, *prev)
		}
		prev = nil
		if cur.c-1 > 0 {
			prev = &item{cur.c - 1, cur.ch}
		}
	}
	if prev != nil {
		return ""
	}
	return string(res)
}

class MinHeap {
    constructor(less) { this.a = []; this.less = less; }
    get size() { return this.a.length; }
    push(x) {
        const a = this.a; a.push(x);
        for (let i = a.length - 1; i > 0;) {
            const p = (i - 1) >> 1;
            if (!this.less(a[i], a[p])) break;
            [a[i], a[p]] = [a[p], a[i]]; i = p;
        }
    }
    pop() {
        const a = this.a, top = a[0], last = a.pop();
        if (a.length) {
            a[0] = last;
            for (let i = 0; ;) {
                let m = i; const l = 2 * i + 1, r = l + 1;
                if (l < a.length && this.less(a[l], a[m])) m = l;
                if (r < a.length && this.less(a[r], a[m])) m = r;
                if (m === i) break;
                [a[i], a[m]] = [a[m], a[i]]; i = m;
            }
        }
        return top;
    }
}

var reorganizeString = function(s) {
    const cnt = new Map();
    for (const ch of s) cnt.set(ch, (cnt.get(ch) || 0) + 1);
    const heap = new MinHeap((x, y) => x[0] !== y[0] ? x[0] > y[0] : x[1] < y[1]);
    for (const [ch, c] of cnt) heap.push([c, ch]);
    const res = [];
    let prev = null;
    while (heap.size) {
        const [c, ch] = heap.pop();
        res.push(ch);
        if (prev) {
            heap.push(prev);
        }
        prev = c - 1 > 0 ? [c - 1, ch] : null;
    }
    return prev ? '' : res.join('');
};

class MinHeap<T> {
    private a: T[] = [];
    constructor(private less: (x: T, y: T) => boolean) {}
    get size(): number { return this.a.length; }
    push(x: T): void {
        const a = this.a; a.push(x);
        for (let i = a.length - 1; i > 0;) {
            const p = (i - 1) >> 1;
            if (!this.less(a[i], a[p])) break;
            [a[i], a[p]] = [a[p], a[i]]; i = p;
        }
    }
    pop(): T {
        const a = this.a, top = a[0], last = a.pop()!;
        if (a.length) {
            a[0] = last;
            for (let i = 0; ;) {
                let m = i; const l = 2 * i + 1, r = l + 1;
                if (l < a.length && this.less(a[l], a[m])) m = l;
                if (r < a.length && this.less(a[r], a[m])) m = r;
                if (m === i) break;
                [a[i], a[m]] = [a[m], a[i]]; i = m;
            }
        }
        return top;
    }
}

function reorganizeString(s: string): string {
    const cnt = new Map<string, number>();
    for (const ch of s) cnt.set(ch, (cnt.get(ch) || 0) + 1);
    const heap = new MinHeap<[number, string]>((x, y) => x[0] !== y[0] ? x[0] > y[0] : x[1] < y[1]);
    for (const [ch, c] of cnt) heap.push([c, ch]);
    const res: string[] = [];
    let prev: [number, string] | null = null;
    while (heap.size) {
        const [c, ch] = heap.pop()!;
        res.push(ch);
        if (prev) {
            heap.push(prev);
        }
        prev = c - 1 > 0 ? [c - 1, ch] : null;
    }
    return prev ? '' : res.join('');
}

载入编辑器，自己跑一遍 →

其他解法

堆的做法每步选剩余最多的字母，可推广到“相同字母至少隔 k 个”的问题；奇偶填充更快更短，但只适用于相邻不同这一情形。

解法 2：计数 + 奇偶下标填充时间 O(n + k)，空间 O(k)

统计每个字母的次数。若最多的字母出现次数超过 (n + 1) / 2，无解。否则先把最多的字母依次放在下标 0、2、4…，再把其余字母接着放在剩余的偶数下标，偶数下标用完后从 1 开始放奇数下标。同一字母在这个顺序里是连续放的，且次数不超过一半，所以它们在字符串中都隔开至少一个位置。

不需要堆，线性时间完成。先放最多的字母是关键，否则它可能从偶数下标末尾绕到奇数下标开头时与自己相邻，正确性需要稍加证明。

class Solution:
    def reorganizeString(self, s: str) -> str:
        n = len(s)
        cnt = [0] * 26
        for ch in s:
            cnt[ord(ch) - 97] += 1
        top = max(range(26), key=lambda c: cnt[c])
        if cnt[top] > (n + 1) // 2:
            return ''
        res = [''] * n
        idx = 0
        order = [top] + [c for c in range(26) if c != top]
        for c in order:
            for _ in range(cnt[c]):
                if idx >= n:
                    idx = 1
                res[idx] = chr(97 + c)
                idx += 2
        return ''.join(res)

class Solution {
    public String reorganizeString(String s) {
        int n = s.length();
        int[] cnt = new int[26];
        for (char ch : s.toCharArray()) cnt[ch - 'a']++;
        int top = 0;
        for (int c = 1; c < 26; c++) if (cnt[c] > cnt[top]) top = c;
        if (cnt[top] > (n + 1) / 2) return "";
        char[] res = new char[n];
        int idx = 0;
        for (int t = 0; t < 26; t++) {
            int c = t == 0 ? top : (t <= top ? t - 1 : t);
            for (int k = 0; k < cnt[c]; k++) {
                if (idx >= n) idx = 1;
                res[idx] = (char) ('a' + c);
                idx += 2;
            }
        }
        return new String(res);
    }
}

class Solution {
public:
    string reorganizeString(string s) {
        int n = s.size();
        vector<int> cnt(26, 0);
        for (char ch : s) cnt[ch - 'a']++;
        int top = 0;
        for (int c = 1; c < 26; c++) if (cnt[c] > cnt[top]) top = c;
        if (cnt[top] > (n + 1) / 2) return "";
        string res(n, ' ');
        int idx = 0;
        vector<int> order = {top};
        for (int c = 0; c < 26; c++) if (c != top) order.push_back(c);
        for (int c : order) {
            for (int k = 0; k < cnt[c]; k++) {
                if (idx >= n) idx = 1;
                res[idx] = 'a' + c;
                idx += 2;
            }
        }
        return res;
    }
};

func reorganizeString(s string) string {
	n := len(s)
	cnt := make([]int, 26)
	for i := 0; i < n; i++ {
		cnt[s[i]-'a']++
	}
	top := 0
	for c := 1; c < 26; c++ {
		if cnt[c] > cnt[top] {
			top = c
		}
	}
	if cnt[top] > (n+1)/2 {
		return ""
	}
	res := make([]byte, n)
	idx := 0
	order := []int{top}
	for c := 0; c < 26; c++ {
		if c != top {
			order = append(order, c)
		}
	}
	for _, c := range order {
		for k := 0; k < cnt[c]; k++ {
			if idx >= n {
				idx = 1
			}
			res[idx] = byte('a' + c)
			idx += 2
		}
	}
	return string(res)
}

var reorganizeString = function(s) {
    const n = s.length;
    const cnt = new Array(26).fill(0);
    for (const ch of s) cnt[ch.charCodeAt(0) - 97]++;
    let top = 0;
    for (let c = 1; c < 26; c++) if (cnt[c] > cnt[top]) top = c;
    if (cnt[top] > Math.floor((n + 1) / 2)) return '';
    const res = new Array(n);
    let idx = 0;
    const order = [top];
    for (let c = 0; c < 26; c++) if (c !== top) order.push(c);
    for (const c of order) {
        for (let k = 0; k < cnt[c]; k++) {
            if (idx >= n) idx = 1;
            res[idx] = String.fromCharCode(97 + c);
            idx += 2;
        }
    }
    return res.join('');
};

function reorganizeString(s: string): string {
    const n = s.length;
    const cnt: number[] = new Array(26).fill(0);
    for (const ch of s) cnt[ch.charCodeAt(0) - 97]++;
    let top = 0;
    for (let c = 1; c < 26; c++) if (cnt[c] > cnt[top]) top = c;
    if (cnt[top] > Math.floor((n + 1) / 2)) return '';
    const res: string[] = new Array(n);
    let idx = 0;
    const order: number[] = [top];
    for (let c = 0; c < 26; c++) if (c !== top) order.push(c);
    for (const c of order) {
        for (let k = 0; k < cnt[c]; k++) {
            if (idx >= n) idx = 1;
            res[idx] = String.fromCharCode(97 + c);
            idx += 2;
        }
    }
    return res.join('');
}

栈与堆专题的其他题目

查看栈与堆全部题目 →