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

LeetCode 767.重构字符串

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

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

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

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

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

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

通过次数13,259
提交次数30,089

思路:基于计数的贪心算法:按照每个字符出现的频率进行排序,因此当字符相同时会连续出现,每隔一个位置插入一个字符,并且保证出现次数最多的字母排在最后并从小到大排序即可。

class Solution {
    public String reorganizeString(String S) {	
    	int len=S.length();
    	int[] nums=new int[26];  	
    	for(char c : S.toCharArray()) 
            nums[c-'a']+=100;
    	for(int i=0;i<26;i++) 
            nums[i]+=i;   	
    	Arrays.parallelSort(nums); 	
    	int t=1;
    	char[] ans=new char[len];  	
    	for(int num : nums) {
    		int ct=num/100;
    		char ch=(char)('a'+(num%100));
    		if(ct>(len+1)/2) return "";
    		for(int i=0;i<ct;i++) {
    			if(t>=len) t=0;
    			ans[t]=ch;
    			t+=2;
    		} 
    	}   	
    	return new String(ans);
    }
}