-
Notifications
You must be signed in to change notification settings - Fork 0
/
1791 D. Distinct Split.cpp
134 lines (133 loc) · 4.09 KB
/
1791 D. Distinct Split.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
/*
problem link: https://codeforces.com/contest/1791/problem/D
my solution on codeforces : https://codeforces.com/contest/1791/submission/192805049
problem name: D. Distinct Split
status: accepted
author: LELLO
*/
#include <bits/stdc++.h>
#include <iostream>
#include <chrono>
#include <vector>
#include <set>
#include <map>
#include<math.h>
#include <stack>
#include <cmath>
#include <unordered_map>
#include <algorithm>
#include <iomanip>
#include <bitset>
#include <utility>
#include <string>
#include <cctype>
#include <iomanip>
#include <numeric> // for NTH
#define bye return;
#define endl '\n'
#define ll long long
#define li long int
#define lli long long int
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) ((x).size())
#define ison(num, bit) (num & (1 << bit))
#define setoffif(num, bit) (num ^= (1 << bit)) // iff (num &(1<<bit))
#define setoff(num, bit) (num &= ~(1 << bit))
#define seton(num, bit) (num |= (1 << bit))
#define flipbit(num, bit) (num ^= (1 << bit))
#define LSB(num) (num & (-num))
#define pop_count_int(num) __builtin_popcount(num)
#define pop_count_l(num) __builtin_popcountl(num)
#define pop_count_ll(num) __builtin_popcountll(num)
#define clz(num) __builtin_clz(num)
#define clzll(num) __builtin_clzll(num)
#define ctz(num) __builtin_ctz(num)
#define ctzll __builtin_ctzll
#define Num_of_Digits(n) ((ll)log10(n) + 1)
#define ceill(n, m) (((n) / (m)) + (((n) % (m) ) ? 1 : 0))
#define lastOne(x) (__builtin_clzll(x))
#define fixed(n) fixed << setprecision(n)
#define lb(c, x) distance((c).begin(), lower_bound(all(c), (x)))
#define ub(c, x) distance((c).begin(), upper_bound(all(c), (x)))
#define Time cerr << "Time Taken: " << (float)clock() / CLOCKS_PER_SEC << " Secs" << "\n";
#define Pi 3.14159265358979323846264
#define INF 0x3f3f3f3f
#define sin(a) sin((a)*PI/180)
#define cos(a) cos((a)*PI/180)
#define yes cout << "YES" << endl;
#define no cout << "NO" << endl;
#define M 32
ll sgn(ll x){ if(x > 0) return 1; if(x < 0) return -1; return 0;}
ll mod = 1e9 + 7;
ll mul(ll a, ll b) { return ((a % mod) * (b % mod)) % mod; }
ll add(ll a, ll b) { return ((a % mod) + (b % mod)) % mod; }
ll sub(ll a, ll b) { return ((a % mod) - (b % mod) + mod) % mod; }
const ll llmin = -1e18 ;
const ll llmax = 1e18 ;
const int imin = -1e9 ;
const int imax = 1e9 ;
const int N = 2e5 ;
using namespace std;
void AC() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr); // or cin.tie(NULL)
cout.tie(nullptr); // or cout.tie(0)
}
void file_set(){ //string& file_name
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
// freopen((file_name+".in").c_str(), "r", stdin);
// freopen((file_name+".out").c_str(), "w", stdout);
}
bool sortbysec(const pair<int,int> &a,const pair<int,int> &b)
{
return (a.second < b.second);
}
// THOSE WHO CAN'T REMEMBER THE PAST'RE CONDEMNED TO REPEAT IT (USE DP -_-) - George Santayana
// PUSH HARDER THAN YESTERDAY IF YOU WANT A DIFFERENT TOMORROW !
//YOU DON'T HAVE TO BE A GENIUS , YOU NEED TO BE DETERMINED .
const ll int MAX = 6e6;
ll int dp[MAX] ;
const ll LOO = 0x3f3f3f3f3f3f3f3f;
const int OO = 0x3f3f3f3f;
void LELLO(){
int n ; cin >> n ;
string s ; cin >> s ;
map<char , ll > mp , mp2 ;
for (int i = 0; i < n; i++)
{
mp[s[i]] ++ ;
}
ll mx = llmin , co1(0) , co2(mp.size()) ;
for (auto val : s)
{
mp2[val] ++ ;
co1 += (mp2[val]== 1) ;
co2 -= (mp[val] == 1) ;
mp[val]--;
mx = max(mx , co1+co2) ;
}
cout<< mx <<endl;
bye
}
void driver(ll t=1)
{
while (t--) LELLO();
Time
}
signed main()
{
AC();
// file_set();
ll test ; cin >> test ;
// chrono::time_point<chrono::system_clock> start, end;
// start = chrono::system_clock::now();
driver(test);
// end = chrono::system_clock::now();
// chrono::duration<double> elapsed_seconds = end - start;
// time_t end_time = chrono::system_clock::to_time_t(end);
// cout << "finished computation at " << ctime(&end_time) << "elapsed time: " << elapsed_seconds.count() << "s\n";
}