[Codeforces Round 849 (Div. 4)] D. Distinct Split

 

---

https://codeforces.com/blog/entry/112282

Codeforces Round #849 (Div. 4) Editorial - Codeforces

#include "bits/stdc++.h"
using namespace std;
 
#define ll long long

#define          all(v)              v.begin(), v.end()
#define         rall(v)              v.rbegin(),v.rend()
 
#define            pb                push_back
#define          sz(a)               (int)a.size()

void solve() {
    int n; string s; cin >> n >> s;
    vector<int> cnt(26, 0), p(26, 0);
    for(auto x: s) cnt[x - 'a']++;
    int ans = 0;
    for(auto x: s) {
        --cnt[x - 'a'];
        ++p[x - 'a'];
        int cur = 0;
        for(int i = 0; i < 26; ++i) {
            cur += min(1, cnt[i]) + min(1, p[i]);
        }
        ans = max(ans, cur);
    }
    cout << ans << "\n";
}   
 
int32_t main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    cin >> t;
    while(t--) {
        solve();
    }
}

s   j   j   n   o   s   t   j   v   z   i   h   h   d   q   h   t   c   j

 

1  2 / 3  4   5   6  7  -   8   9 10 11  -   12  13 -  -   14  -

 

1  2   -   3   4   5  6 / 7  8  9  10 11 -   12  13 -  14 15

 

※. 배열 2개를 생성한 후 배열1에 문자열의 정보를 저장한다.

 

※. 문자열을 탐색하며 str.charAt(현재)의 char은 배열1에서 빼준 뒤 배열2에 넣어준다

(배열1 = f(a), 배열2 = f(b) )

 

※. a~z까지 탐색하며 가장큰 ans를 찾는다.

 

※. 중복된 알파벳은 최대 1개만 포함

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		//StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int T = Integer.parseInt(br.readLine());
		while(T --> 0) {
			int N = Integer.parseInt(br.readLine());
			String str = br.readLine();
			int sum = 0;
			int[]arr = new int[26];
			int[]arr1 = new int[26];
			for(int i = 0; i < str.length(); i++) {
				int temp = str.charAt(i) - 'a';
				arr[temp]++;
			}
			for(int j = 0; j < str.length(); j++) {
				int temp = str.charAt(j)-'a';
				arr[temp]--;
				arr1[temp]++;
				int cur = 0;
				for(int i = 0; i < 26; i++) {
					cur += Math.min(1, arr[i]) + Math.min(1, arr1[i]);
				}
				sum = Math.max(sum, cur);
			}
			sb.append(sum).append('\n');
		}
		System.out.println(sb);
	}
}