767.Reorganize String === ###### tags: `Medium` `String` `Hash Table` `Greedy` `Sorting` `Heap` `Counting` [767. Reorganize String](https://leetcode.com/problems/reorganize-string/) ### 題目描述 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 ```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(''); } ``` > 寫得好冗,晚點有空再來優化一下 > [name=Marsgoat][time=23 Aug 2023] #### C# ```csharp= 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); } } } ``` > [name=Jim][time=23 Aug 2023] #### TypeScript ```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(''); } ``` > [name=sheep][time=24 Aug 2023] ### Reference [回到題目列表](https://marsgoat.github.io/XNnote/coding/leetcodeEveryDay.html)