【牛客面试真题】字符串操作

腾讯音乐娱乐集团2023校园招聘技术类岗位编程题一

字符串操作

给定一个只包含小写字母字符串，每次可以选择两个相同的字符删除，并在字符串结尾新增任意一个小写字母。请问最少多少次操作后，所有的字母都不相同？

输入例子：
“abab”
输出例子：
2
例子说明：
第一次操作将两个’a’变成一个’f’，字符串变成"bbf"。
第二次操作将两个’b’变成一个’b’，字符串变成"fb"。
操作方式不是唯一的，但可以证明，最少操作次数为2。

import java.util.*;

class Solution {
    public int minOperations (String str) {
        int[] counts = new int[26];
        for (char c : str.toCharArray()) {
            ++counts[c - 'a'];
        }
//        System.out.println(Arrays.toString(counts));
//        System.out.println(counts.length);

        int result = 0;//最后返回的合并次数
        int sum = 0;//sum统计合成的次数
        int countZero = 0;//除完2等于0的单词数

        //遍历26个字母对应的值
        for (int i = 0; i < 26; ++i) {
            sum += counts[i] / 2;//sum统计合成的次数
            //更新26个字母对应的次数，取余数
            counts[i] %= 2;
            if (counts[i] == 0) {
                ++countZero;
            }
        }
        //除完2等于0的单词数 比 合成的次数 大，说明空的字符比需要合成的多，不用再次合成
        if (sum < countZero) {
            return sum;
        }

        result += sum;
        result += sum - countZero;

        return result;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        Integer result = solution.minOperations("abab");

        System.out.println(result);
    }
}