[Codeforces Round #780 (Div. 3)] C. Get an Even String

 

 

---

※ n은 기존 문자열 길이, m은 조건을 만족하는 문자열 길이

※ 문자열의 길이 n을 구한 뒤 조건을 만족하는 2개의 문자가 있다면 m에 2씩 더한 뒤 n-m을 한다.

※ a-z 까지 받을 수 있는 배열을 만든 후 문자열을 만든 후 같은 문자를 2개 받는다면 m에 2를 더해준 뒤

   배열을 초기화 한다.

※ 문자를 받은 후 같은 문자가 있다면 m += 2를 하고 이전 까지 탐색했던 문자는 버린다.

   가장 먼저 짝을 이루는 문자가 최적이다. [a,b,c,d,b,a]에서 bb나 aa둘 다 가능하지만 짝을 이루는 i번째 문자 까지는 

   먼저 짝을 이루는 문자가 가장 적은 문자를 삭제하기 때문이다.

   (맨 처음 짝을 이룬 i번째 문자 이전의 짝을 이루지 못한 수만 제거하면 되기 때문에)

   (이걸 응용해 dp로도 이 문제를 풀 수 있다 0~n까지 탐색하며 i번째에 가장 긴 m을 차례로 만들면 되기 때문)

 

1. 26개의 불리언 배열을 만든다.

2. 문자열의 문자를 탐색하며 (a-z)까지의 알파벳이 배열에 없었다면 false -> true로 바꿈

3. 문자를 탐색했는데 true 라면 m(가능한 문자)에 2를 더한 뒤 배열을 초기화

4. 삭제해야 하는 문자 수 = n(문자열 길이) - m(짝을 이루는 문자열 길이)

 

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.TreeSet;
public class Main {
 	public static void main(String arg[]) throws IOException {
 		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 		int T = Integer.parseInt(br.readLine());
 		while(T --> 0) {
 			String str = br.readLine();
 			int n = str.length();
 			boolean[] prev = new boolean[26];
 			int m = 0;
 			for(int i = 0; i < str.length(); i++) {
 				int a = str.charAt(i) - 'a';
 				if(prev[a] == true) {
 					m += 2;
 					prev = new boolean[26];
 				}
 				else {
 					prev[a] = true;
 				}
 			}
 			System.out.println(n-m);
 		}
 	}
}