767.Reorganize String

tags: `Medium` `String` `Hash Table` `Greedy` `Sorting` `Heap` `Counting`

題目描述

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.

解答

Javascript











































function reorganizeString(s) {
  const map = new Map();
  for (const c of s) {
    map.set(c, map.get(c) + 1 || 1);
  }

  const sort = [...map.entries()].sort((a, b) => b[1] - a[1]);
  if (sort[0][1] > (s.length + 1) / 2) return '';

  const result = [];

  while (map.size) {
    const keys = [...map.keys()];
    keys.sort((a, b) => map.get(b) - map.get(a));
    const first = keys[0];
    const second = keys[1];

    if (map.get(first) === 1) {
      map.delete(first);
    } else {
      map.set(first, map.get(first) - 1);
    }

    if (map.get(second) === 1) {
      map.delete(second);
    } else {
      map.set(second, map.get(second) - 1);
    }

    result.push(first);
    if (second) result.push(second);

    if (map.size === 1) {
      const last = [...map.keys()][0];
      if (map.get(last) > 1) return '';

      result.push(last);
      map.delete(last);
    }
  }

  return result.join('');
}

寫得好冗，晚點有空再來優化一下
Marsgoat23 Aug 2023

C#










































public class Solution {
    public string ReorganizeString(string s) {
        int[] letterCounts = new int[26];
        foreach (char c in s) {
            letterCounts[c - 'a'] += 1;
        }
        // 字母照出現次數排序
        char[] sorted = "abcdefghijklmnopqrstuvwxyz"
                .OrderByDescending(c => letterCounts[c - 'a']).ToArray();
        
        int max = letterCounts[sorted[0] - 'a'];
        if (max > (s.Length + 1) / 2) return string.Empty;

        char[] ans = new char[s.Length];
        int ansIndex = 0;
        foreach (char c in GetNextLetter()) {
            ans[ansIndex] = c;
            ansIndex += 2;
            if (ansIndex >= s.Length) {
                ansIndex = 1;
            }
        }

        return new string(ans);

        IEnumerable<char> GetNextLetter() {
            int sortedIndex = 0;
            int count = letterCounts[sorted[sortedIndex] - 'a'];

            do
            {
                yield return sorted[sortedIndex];
                
                if (--count == 0)
                {
                    if (++sortedIndex == 26) break;
                    count = letterCounts[sorted[sortedIndex] - 'a'];
                }
            } while (count > 0);
        }
    }
}

Jim23 Aug 2023

TypeScript

function reorganizeString(s: string): string {
  const n = s.length;
  const hashTable = new Map<string, number>();

  for (let i = 0; i < s.length; i++) {
    hashTable.set(s[i], (hashTable.get(s[i]) ?? 0) + 1);
  }

  // 按次數降序排列字元
  const chars = [...hashTable.keys()];
  chars.sort((a, b) => hashTable.get(b)! - hashTable.get(a)!);
  // 最多重複字元是否大於長度的一半
  if (hashTable.get(chars[0])! > (n + 1) >> 1) return '';

  // 放置字元
  let result: string[] = new Array(n).fill('');
  let index = 0;
  for (const char of chars) {
    const count = hashTable.get(char)!;
    for (let i = 0; i < count; i++) {
      if (index >= result.length) index = 1;
      result[index] = char;
      index += 2;
    }
  }

  return result.join('');
}

sheep24 Aug 2023

Reference

回到題目列表