题目

Problem Description
Given a string, you use some letters or digits to creat a new string, this new string have three properties.
1.any two adjacent letter aren't the same.
2.the new string have the biggest length.
3.the new string have the biggest lexicographical ordering.
Input
The input consists of multiple test cases. Each test case contain a string, the string is consist of 'a'~'z', 'A' - 'Z' and '0' - '9'. the length of string is not exceed 500.
Output
For each case, print the new string.
Sample Input

2
abaa
001

Sample Output

aba
010

题目分析

题意是：输入一个包含 'a'~'z', 'A' - 'Z' 和'0' - '9'的长度不大于500的字符串，要求根据输入字符串创建一个符合以下规则的新字符串：相邻字符不能相同，最大长度，字典排序的最大序列。

具体代码

public class BestString {

    public String handle(String input){
        char[] characters = input.toCharArray();
        characters = permutationWithDictionary(characters);//对数组进行字典排序获取最大序列
        //保证相邻字符不相同
        StringBuffer sb = new StringBuffer();
        StringBuffer temp = new StringBuffer();
        for (char c : characters) {
            if (sb.length()>0) {
                if (c != sb.charAt(sb.length()-1)) {
                    sb.append(c);
                }else{
                    temp.append(c);
                }
            }else{
                sb.append(c);
            }
        }
        if (temp.length()>0) {
            String tempStr = handle(temp.toString());//递归调用
            if (sb.charAt(sb.length()-1) != tempStr.charAt(0)) {
                sb.append(tempStr);
            }       
        }
        return sb.toString();
    }
    
    //获取字典排序的最大序列
    public  char[] permutationWithDictionary(char[] characters){
        while(true){
            for (int i = characters.length-1; i >=0; i--) {
                for (int j = 0; j < i; j++) {
                    if (characters[i]>characters[j]) {
                        char temp = characters[i];
                        characters[i] = characters[j];
                        characters[j] = temp;
                        break;
                    }
                }
            }
            //从右向左找到第一个非递增的元素,若找不到则返回结果
            for(int k=characters.length-2;k>=0;k--){    
                if(characters[k]<characters[k+1]){
                    break;                   
                }else if(k==0){
                    return characters;
                }
            }  

        }
    }
    
}