GoCalf Calf 的自留地 · 昙花一现

767. Reorganize String

Calf

Problem

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.

https://leetcode.com/problems/reorganize-string/

Example 1:

Input: s = "aab"
Output: "aba"

Example 2:

Input: s = "aaab"
Output: ""

Constraints:

  • 1 <= s.length <= 500
  • s consists of lowercase English letters.

Test Cases

python 
class Solution:
    def reorganizeString(self, s: str) -> str:
solution_test.py下载完整源码
py 
import pytest

from solution import Solution


def verify(res, s):
    assert sorted(res) == sorted(s)
    prev = res[0]
    for i in range(1, len(s)):
        assert prev != res[i]
        prev = res[i]


@pytest.mark.parametrize('s, expected', [
    ("aab", "aba"),
    ("aaab", ""),

    ("vvvlo", "vlvov"),
    ("aabbcc", "abacbc"),
])
@pytest.mark.parametrize('sol', [Solution()])
def test_solution(sol, s, expected):
    res = sol.reorganizeString(s)
    if expected == '':
        assert res == ''
    else:
        assert res != ''
        if res != expected:
            verify(res, s)

Thoughts

判定是否可行很简单，显然如果有一个字符的出现次数大于 ⌈n/2⌉\lceil n/2\rceil 就不可行，否则可行。

开始以为重新排列 s 的逻辑类似于 2182. Construct String With Repeat Limit，相当于 repeatLimit = 1，且不限定字符的顺序。但是因为要求是用掉所有的字符（当可行的时候），重建的逻辑就还是会有些不同。Problem 2182 中因为要让结果字符串按字典序最大，每次都先取最大的字符，却并不保证所有字符都能用上。

本题需要把所有的字符都用上，可以考虑建一个词频的最大堆（词频相同时按字符的字典序），每次从堆中取出词频最大的两个字符，添加到结果字符串末尾。把两个字符以及剩余的词频（如果还大于零）放回到堆中。因为词频相同的字符会按字典序排序，本次取出的第二个字符一定不会跟下一次取出的第一个字符相同，不会产生连续重复字符。

最后如果堆里只剩下一个字符（显然剩余的词频只能是 1），将其加到结果字符串的末尾即可。

时间复杂度 O(n log C)，空间复杂度 O(C)，其中 C 是 s 中各不相同的字符总数，题目中 C ≤ 26 可以认为是常数。

Code

solution.py下载完整源码
py 
from heapq import heapify, heappop, heappush, heapreplace
from typing import Counter


class Solution:
    def reorganizeString(self, s: str) -> str:
        counts = Counter(s)
        if max(counts.values()) > ((len(s) + 1) >> 1):
            return ''

        parts = []
        queue = [(-f, c) for c, f in counts.items()]
        heapify(queue)
        while len(queue) > 1:
            f1, c1 = heappop(queue)
            f2, c2 = queue[0]
            parts.append(c1)
            parts.append(c2)
            f1 += 1
            f2 += 1
            if f2:
                heapreplace(queue, (f2, c2))
                heappush(queue, (f1, c1))
            elif f1:
                heapreplace(queue, (f1, c1))
            else:
                heappop(queue)

        if queue:
            parts.append(queue[0][1])

        return ''.join(parts)

评论需要 JavaScript。