题目 #

题目描述 #

给定一个只包含小写字母的字符串，每次操作可以将两个相同的字母删除，然后在字符串的末尾新增任意一个小写字母。请问最少需要多少次操作，才能使字符串中所有的字母都不相同。

输入描述 #

第一行是一个整数 N，表示后续会有 N 个字符串，每个字符串占一行。

输出描述 #

对于输入的每一个字符串，你需要输出该字符串所需的最少操作次数，每个输出占一行。

输入示例 #

1
abab

输出示例 #

提示信息 #

第一次操作将两个’a’删除，并在字符串末尾新增一个’f’，字符串变为"bbf"；

第二次操作将两个’b’删除，并在字符串末尾新增一个’b’，字符串变为"fb"；

操作方式并不是唯一的，但是可以证明，最少操作次数为2。

1 < N < 100； 1 < S.length < 1000.

解答 #

1 笨办法 #

import java.io.*;
import java.util.*;

public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out=new PrintWriter(System.out);
        String line;
        line=in.readLine();
        int n=Integer.parseInt(line);
        while(n>0){
            int[] charNum=new int[26];
            line=in.readLine();
            char[] charArr=line.toCharArray();
            int leaveSize=26;
            for(char ch:charArr){
                charNum[ch-'a']++;
                if(charNum[ch-'a']==1)leaveSize--;
            }
            int num=0;
            boolean hasLeaf=true;
            for(int i=0;i<26;i++){
                if(charNum[i]==2){
                    num+=1;
                }
                else if(charNum[i]>1){
                    //奇数
                    if(charNum[i]%2==1){
                        if(hasLeaf&&leaveSize*2>=charNum[i]-1){
                            num+=(charNum[i]-1)/2;
                            leaveSize-=(charNum[i]-1)/2;
                            if(leaveSize==0){
                                hasLeaf=false;
                            }
                        }else if(hasLeaf&&leaveSize*2<charNum[i]-1){
                            hasLeaf=false;
                            num+=leaveSize;
                            num+=(charNum[i]- leaveSize*2-1 );
                            leaveSize=0;
                        }else{
                            num+=charNum[i]-1;
                        }
                    }
                    //偶数
                    else{
                        if(hasLeaf&&leaveSize*2>=charNum[i]-2){
                            num+=(charNum[i]-2)/2+1;
                            leaveSize-=(charNum[i]-2)/2;
                            if(leaveSize==0){
                                hasLeaf=false;
                            }
                        }else if(hasLeaf&&leaveSize*2<charNum[i]-2){
                            hasLeaf=false;
                            num+=leaveSize;
                            num+=(charNum[i]- leaveSize*2 -1);
                            leaveSize=0;
                        }else{
                            num+=charNum[i]-1;
                        }
                    }
                }
            }
            out.println(num);
            n--;
        }
        out.flush();
    }
}

方法的思路：首先分析在进行重复处理的过程中，存在两个情况：

在字符串中出现的字符总的数量没有达到26个，此时可以将一些超过1个的字符转为现在不存在的字符，在这种情况下，也存在两个情况：
- 剩余的字母超过现在需要的字符，比如剩余10个字符，其可以充当20个重复字符的数量，因此小于20的字符出现次数，可以被全部进行替换
- 剩余的字母已经不够用了，这时候，能够用多少就用多少，剩下的转移到最下面的那种情况
- 在实际处理的过程中，其实奇数偶数存在一点点差别：
  - 奇数，例如aaaaa，其实只需要**拿出四个aaaa**即可，剩余的一个已经是单独的，所以是(字符次数-1)/2
  - 偶数的话，比如aaaaaa，实际上转换为其他的剩余字符，只需要转换aaaa，4个a即可，因为剩余的aa可以自己转为a，因此实际上的执行次数是(字符次数-2)/2+1
出现的字符串已经达到26个了，现在已经没有办法进行转换了，因为全部的字符都被用光了，要转换只能转换成自己，比如aaaa只能一步步的转为a，这个过程要持续3次，次数是字符长度-1

时间复杂度 #

$O(N)$

2 另一种思路 #

import java.io.*;
import java.util.*;

public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out=new PrintWriter(System.out);
        String line;
        line=in.readLine();
        int n=Integer.parseInt(line);
        while(n>0){
            int[] charNum=new int[26];
            line=in.readLine();
            char[] charArr=line.toCharArray();
            int leaveSize=26;
            for(char ch:charArr){
                charNum[ch-'a']++;
            }
            int num=0;
            int charLocalNum=0;
            for(int i=0;i<26;i++){
                if(charNum[i]==0)continue;
                if(charNum[i]==1){
                    charLocalNum+=1;
                }
                else if(charNum[i]%2==1){
                    num+=charNum[i]/2;
                    charLocalNum+=charNum[i]/2+1;
                }else if(charNum[i]%2==0){
                    num+=charNum[i]/2;
                    charLocalNum+=charNum[i]/2;
                }
            }
            if(charLocalNum>26){
                num+=charLocalNum-26;
            }
            out.println(num);
            n--;
        }
        out.flush();
    }
}

这个方法的主要思想其实是：

首先将全部的出现过的字符转化为单个字符，在转换的过程中，
- 奇数变成单个字符，需要变换个数/2次，占用的位置是个数/2+1个位置
- 偶数变化，变换个数/2次，占用的位置是个数/2+1个位置
在全部变成单个的字符之后，字符占用的位置有可能超过26个位置，这样就不够用，但是可以将多余出来的全部字符占用位置都堆在某一个字符上，假如a上，此时26个字符全部占完，但是a还多一些，具体多的是多出来元素，a的长度是多出来元素+1，将其转为单个a的次数是多出来元素+1 -1次