企业官网建设流程全解析

767. 重构字符串 - 力扣（LeetCode）767. 重构字符串 - 给定一个字符串 s ，检查是否能重新排布其中的字母，使得任意两个相邻字符不相同。返回 s 的任意可能的重新排列。若不可行，返回空字符串 "" 。 示例 1:输入: s = "aab"输出: "aba"示例 2:输入: s = "aaab"输出: "" 提示: * 1 <= s.length <= 500 * s 只包含小写字母https://leetcode.cn/problems/reorganize-string/

题目描述

给定一个字符串s，检查是否能重新排布其中的字母，使得两相邻字符不同。

若可行，输出任意可行的结果。若不可行，返回空字符串""。

示例 1 输入:s = "aab"输出:"aba"

示例 2 输入:s = "aaab"输出:""

核心判定条件：出现次数最多的字符，次数不能大于(n+1)/2，大于则一定无法构造，直接返回空串。

解法

和前面一题基本相似,这里不过多赘述

class Solution { public: string reorganizeString(string s) { unordered_map<int,int>hash; sort(s.begin(), s.end()); cout<<s<<endl; int maxnum=0; char target; for(auto e:s) { hash[e]++; if(hash[e]>maxnum) { maxnum=hash[e]; target=e; } } int n=s.size(); string ret(n,'1'); if(maxnum>(n+1)/2) return ""; for(int i=0;i<n;i++) { if(s[i]==target) { int j=0; while(j<n) { ret[j]=s[i]; i=(i+1)%n; j+=2; } j=1; while(j<n) { ret[j]=s[i]; i=(i+1)%n; j+=2; } break; } } return ret; } };