Codeforces Round #849 (Div. 4) 1791D. Distinct Split Solution

                                          

 Problem Link :  https://codeforces.com/contest/1791/problem/D

Solution in C++:

1. /// La ilaha illellahu muhammadur rasulullah
2. ///******Bismillahir-Rahmanir-Rahim******///
3. /// Abul Hasnat Tonmoy
4. /// Department of CSE,23rd batch
5. /// Islamic University,Bangladesh
6. ///**********ALLAH IS ALMIGHTY************///
7. #include <bits/stdc++.h>
8. using namespace std ;
9. int32_t main() {
10. ios_base::sync_with_stdio(0);
11. cin.tie(0);
12. int t ;
13. cin >> t ;
14. while ( t-- ){
15. int n ;
16. cin >> n ;
17. string s ;
18. cin >> s ;
19. std::vector<int> pre(n,0),sup(n,0);
20. set<char>st ;
21. for ( int i = 0 ; i < n ; i++ ){
22. st.insert(s[i]) ;
23. pre[i] = st.size() ;
24. }
25. st.clear();
26. for ( int i = n-1 ; i >= 0 ; i-- ){
27. st.insert(s[i]) ;
28. sup[i] = st.size() ;
29. }
30. st.clear();
31. int ans = 0 ;
32. for ( int i = 0 ; i < n-1 ; i++ ){
33. ans = max ( ans , sup[i+1]+pre[i]) ;
34. }
35. cout << ans<< endl;
36. st.clear() ;
37. }
38. return 0 ;
39. }