Codeforces Round 859 (Div. 4) 1807C - Find and Replace Solution

   

Problem Link :  https://codeforces.com/contest/1807/problem/C

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. string s1, s2 ;
20. for ( int i = 0 ; i < n ; i++) {
21. if ( i % 2 == 0) {
22. s1.push_back('0');
23. s2.push_back('1');
24. }
25. else {
26. s1.push_back('1');
27. s2.push_back('0');
28. }
29. }
30. map < char ,char > mp1 , mp2 ;
31. bool x = true , y = true ;
32. for ( int i = 0 ; i < n ; i++ ) {
33. if ( mp1.find(s[i])!=mp1.end()){
34. if(mp1[s[i]] != s1[i]) {
35. x = false ;
36. }
37. }
38. else
39. mp1.insert({s[i],s1[i]}) ;
40. }
41. for ( int i = 0 ; i < n ; i++ ) {
42. if ( mp2.find(s[i] )!=mp2.end()){
43. if(mp2[s[i]] != s2[i]) {
44. y = false ;
45. }
46. }
47. else
48. mp2.insert({s[i],s2[i]}) ;
49. }
50. if ( x == true || y == true ) {
51. cout << "YES"<<endl;
52. }
53. else
54. cout <<"NO"<<endl;
55.  
56. }
57. return 0 ;
58. }