欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

leetcode 767.重构字符串

程序员文章站 2024-03-16 16:58:10
...

leetcode 767.重构字符串

题干

给定一个字符串S,检查是否能重新排布其中的字母,使得两相邻的字符不同。
若可行,输出任意可行的结果。若不可行,返回空字符串。

示例 1:
输入: S = “aab”
输出: “aba”

示例 2:
输入: S = “aaab”
输出: “”

注意:
S 只包含小写字母并且长度在[1, 500]区间内。

题解

统计字母出现的次数,根据次数降序排列,然后按照先奇(index=0)后偶的顺序将字母放回S

class Solution {
public:
    string reorganizeString(string S) {
        int n = S.length();
        int head = 0,tail = n-1;
        vector<string> alphaCount(26,"");
        if(n==0){
            return "";
        }else if(n==1){
            return S;
        }
        for(int i = 0 ; i < n ; ++i){
            alphaCount[S[i] - 'a'].push_back(S[i]);
        }   
        //字符串长度即字符出现次数,按照字符出现次数降序排列
        sort(alphaCount.begin(),alphaCount.end(),[&](string a,string b){
            return a.length() > b.length();
        });
        if(alphaCount[0].length() > (n + 1) / 2){
            return "";
        }
        //按照奇偶填充
        int ptr = 0;
        int evenPtr = 1;
        int oddPtr = 0;
        for(int i = 0;i<26;++i){
            while(!alphaCount[i].empty() && oddPtr < n){
                S[oddPtr] = alphaCount[i].back();
                alphaCount[i].pop_back();
                oddPtr += 2;
            }
            while(!alphaCount[i].empty()){
                S[evenPtr] = alphaCount[i].back();
                alphaCount[i].pop_back();
                evenPtr += 2;
            }
        }
        return S;
    }
};
相关标签: leetcode leetcode