Educational Codeforces Round 2 C. Make Palindrome

链接: http://codeforces.com/contest/600/problem/C

public void solve(int testNumber, InputReader in, OutputWriter out) {
        String s = in.readString();
        int[] count = new int[26];
        /**
         * counting the  occurences
         */
        for(int i = 0; i < s.length(); i++) {
            count[s.charAt(i) - 'a']++;
        }

        int i = 0;
        int j  = 25;
        while (i <= j) {
            while (i < count.length && count[i] % 2 == 0) { // find the left side first odd
                i ++;
            }
            while (j >=0 && count[j] % 2 == 0) { // find the right side first odd
                j --;
            }
            // move right to first (because it is asked for the lexicographically (alphabetically) smallest palindrome)
            if (i < count.length) {
                count[i++] ++;
            }
            if (j >=0) {
                count[j--]--;
            }
        }
        StringBuilder sb = new StringBuilder();
        int odd_Index = -1;
        for (int k = count.length - 1; k >=0 ; k--) {
            if (count[k] % 2 != 0) { // we know there is no more than 1 odd number in our count array
                odd_Index = k;
                count[k] --;
            }
            for (int l = 0; l < count[k]; l++) {
                if (l % 2 == 0) {
                    sb.append((char)('a' + k));
                }
                else {
                    sb.insert(0,(char)('a' + k));
                }
            }
        }
        if (odd_Index != -1) {
            sb.insert(sb.length()/2, (char)('a' + odd_Index)); // put the only odd number (if it has) in the middle
        }
        out.print(sb.toString());
    }

这题开始做的时候, 还是很费脑的, 首先要关注题中要求的回文问题, 不难看出是需要计算字符串中字频的奇偶,

然后可以想到, 回文只能有不能超过一种奇数的字符. 但是后边很难想的是, 如何修改才能满足 lexicographically (alphabetically) smallest palindrome(字典序下最小回文). 这时可以看到题中给出的回文都是lower case, 所以用双指针的方法, 前后两个指针扫描字频数组, 找到奇数字频的回文, 然后把字典序大的回文给字典序小的回文.

最后一个考点是重构回文, 这里需要注意的是, 我们上一步中已经通过交换的方式消灭了奇数字频的回文, 但是真的完全消灭了么? 其实不然, 回文是可以有一个奇数的字频的字符存在的, 这个字频的字符应该放在中间. 所以我们这里用odd_index, 起始值为-1(表示没有奇数字频), 如果上一步后odd_index不是-1, 这表示我们发现一个字频

这里有两个小技巧:

第一, 当重构回文的时候, 因为题中要求 If there are several ways to do that you should get the lexicographically (alphabetically) smallest palindrome. 我们需要从大的字符往小的字符扫描count数组重构回文, 因为我们想把大的字符放在中间, 把小的字符放到两边, 这种构建方法确保了构建后的回文是字典序最小的回文. 我们可以用反证法证明这个理论,即, 如果存在一种构建方法,使得构建的回文字典序小于上面的构建方法构建的回文, 那么这种方法构建的回文中的字符在字典序下, 肯定有一位小于上面的方法构建的回文, 字典序是要求字符串从左到右的字符从小到大排列, 而回文是从中间左右对称的, 所以如果存在另一个构建方法, 那么这种构建方法构建的回文左边一定比右边要小, 然而这就是我们上述中的构建方法. 所以并不存在另一个构建方法.

第二, 奇数字频字符的选择. 在出现多个奇数字频字符时, 比如aaabbbccc时, 这里有3a,3b,3c. 那么结果是什么. 正确答案是aabcbcbaa, 数一下, 这里有4a,3b,2c, 我们可以看到我们选择保留中间的b作为仅有的奇数字频字符, 这里为什么我们不选择字典序更小的a? 如果选择a, 我们就有 3a,4b,2c, 这里直观的就可以看出, 这个组成的字符串肯定字典序大于给出的算法. 那如果选择c呢? 我们既有4a,2b,3c, 这个看起来不错? 这个组成的是aabcccbaa, 对比一下aabcbcbaa. 我们发现在第5位的时候, 算法给出的是b,而这种方法是c, 所以还是算法的字典序小, 这个也可以用反证法证明. 所以要保留的奇数字频字符只能是中间的字符, 即这里的b.