C. Get an Even String题解

A字符串a=a1a2…。

即使由由相同字符组成的长度为2的字符串的串联(连接)组成，也会调用。

换句话说，即使同时满足两个条件，字符串a也是：

其长度n为偶数；
对于所有的奇数i(1≤i≤n−1)，ai=ai+1是满足的。

例如，以下字符串是偶数：“”(空字符串)、“TT”、“AABB”、“oooo”和“ttrrroouuuuuuukk”。

以下字符串不是偶数：“aaa”、“abab”和“abba”。

给定由小写拉丁字母组成的字符串s。

找到要从字符串%s中删除以使其相等的最小字符数。

删除的字符不必是连续的。

输入。

第一行输入数据包含一个整数t(1≤t≤104)–测试中的测试用例数。

测试用例的描述如下。

每个测试用例由一个字符串s(1≤|s|≤2⋅105)组成，其中|s|-字符串s的长度。

该字符串由小写拉丁字母组成。

保证所有测试用例上的|s|之和不超过2⋅105。

输出。

对于每个测试用例，打印一个数字–使s成为偶数必须删除的最小字符数。

输入
6
aabbdabdccc
zyx
aaababbb
aabbcc
oaoaaaoo
bmefbmuyw
输出
3
3
2
0
2
7

A string a=a1a2…an is called even if it consists of a concatenation (joining) of strings of length 2 consisting of the same characters. In other words, a string a is even if two conditions are satisfied at the same time:

its length n is even;
for all odd i (1≤i≤n−1), ai=ai+1 is satisfied.
For example, the following strings are even: “” (empty string), “tt”, “aabb”, “oooo”, and “ttrrrroouuuuuuuukk”. The following strings are not even: “aaa”, “abab” and “abba”.

Given a string s consisting of lowercase Latin letters. Find the minimum number of characters to remove from the string s to make it even. The deleted characters do not have to be consecutive.

Input
The first line of input data contains an integer t (1≤t≤104) —the number of test cases in the test.

The descriptions of the test cases follow.

Each test case consists of one string s (1≤|s|≤2⋅105), where |s| — the length of the string s. The string consists of lowercase Latin letters.

It is guaranteed that the sum of |s| on all test cases does not exceed 2⋅105.

Output
For each test case, print a single number — the minimum number of characters that must be removed to make s even.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;


public class Main {
    public static void main(String[] args) throws IOException {
        InputStreamReader input=new InputStreamReader(System.in);
        BufferedReader reader=new BufferedReader(input);
        int t=Integer.parseInt(reader.readLine());
        for (int i=0;i<t;i++)
        {
            String ss= reader.readLine();
            ArrayList list=new ArrayList();
            int sum=0;
            int len=ss.length();
            for (int j=0;j<len;j++)
            {
                if (list.contains(ss.charAt(j)))//判断list里是否有该字符，有则配对上，在list中减去该配对的字符，并清空list，其他字符都被sum计数，因为sum只减了一（该匹配的字符）
                {
                    sum--;
                    list=new ArrayList();
                }
                else
                {
                    sum++;
                    list.add(ss.charAt(j));
                }
            }
            System.out.println(sum);
        }
        input.close();
    }
}