fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define IOS ios_base::sync_with_stdio(false);cin.tie(NULL); 
  5. #define ll long long
  6. #define ff first
  7. #define ss second
  8. #define pb push_back
  9. #define pf push_front
  10. #define mp make_pair
  11. #define pu push
  12. #define pp pop_back
  13. #define in insert
  14. #define ld long double
  15. #define endl '\n'
  16. #define debug cout << "Hold right there sparky.....\n";
  17. #define forn(low,high,i) for(i=low;i<high;i++)
  18. #define forrev(high,low,i) for(i = high; i>= low;i--)
  19. #define trace(x) cerr << #x << ": " << x << " " << endl;
  20. #define all(v) v.begin(),v.end()
  21. #define sz(v) (int)v.size()
  22.  
  23. typedef unordered_map<int,int> umi;
  24. typedef unordered_map<ll,ll> uml;
  25. typedef vector<int> vi;
  26. typedef vector<ll> vl;
  27. typedef vector<vi> vvi;
  28. typedef vector<vl> vvl;
  29. typedef pair<int,int> pii;
  30. typedef pair<ll,ll> pll;
  31. typedef vector<pii> vpii;
  32. typedef vector<pll> vpll;
  33.  
  34. bool comp(pii x,pii y)
  35. {
  36. 	if(x.ff != y.ff)
  37. 		return x.ff > y.ff;
  38. 	else
  39. 		return x.ss > y.ss;
  40. }
  41.  
  42. int main()
  43. {
  44. 	IOS;
  45. 	int t;
  46. 	ll n,i,j,k;
  47. 	cin >> t;
  48. 	string s;
  49. 	while(t--)
  50. 	{
  51. 		cin >> n >> s;
  52. 		ll a,b;
  53. 		b = 0;
  54. 		a = 1;
  55. 		ll cnt[26];
  56. 		n = s.size();
  57. 		memset(cnt,0,sizeof(cnt));
  58. 		ll temp = 1;
  59. 		forn(1,n,i)
  60. 		{
  61. 			if(s[i] == s[i-1])
  62. 				temp++;
  63. 			else
  64. 			{
  65. 				cnt[s[i - 1] - 'a'] = max(cnt[s[i-1] - 'a'],temp);
  66. 				temp = 1;
  67. 			}
  68. 		}
  69. 		cnt[s[n - 1] - 'a'] = max(cnt[s[n-1] - 'a'],temp);
  70. 		ll res = 0;
  71. 		forn(0,26,i)
  72. 		{
  73. 			res += cnt[i];
  74. 		}
  75. 		int alpha,beta,gamma;
  76. 		unordered_map<int,vpll> substr;
  77. 		alpha = s[0] -'a';
  78. 		for(i=1;i<n;i++)
  79. 		{
  80. 			if(s[i] == s[i-1])
  81. 			{
  82. 				a++;
  83. 				alpha = s[i] - 'a';
  84. 			}
  85. 			else
  86. 			{
  87. 				beta = s[i] - 'a';
  88. 				b++;
  89. 				for(j=i+1;j<n;j++)
  90. 				{
  91. 					if(s[j] == s[j-1])
  92. 						b++;
  93. 					else
  94. 						break;
  95. 				}
  96. 				//cout << alpha << "," << beta << " : ";
  97. 				gamma = 27*alpha + beta;
  98. 				//cout << gamma << '\n';
  99. 				i = j - 1;
  100. 				if(i && b)substr[gamma].pb({a,b});
  101. 				alpha = beta;
  102. 				beta = 0;
  103. 				a = b;
  104. 				b = 0;
  105. 			}
  106. 		}
  107. 		int prev_x,prev_y,t;
  108. 		for(auto x : substr)
  109. 		{
  110. 			//cout << x.ff << " : ";
  111. 			sort(all(x.ss),comp);		//Sorted in decreasing order of letter1's frequecy with tie breker as descending order of letter2's frequency
  112. 			res += x.ss[0].ff * x.ss[0].ss;
  113. 			prev_x = x.ss[0].ff;
  114. 			prev_y = x.ss[0].ss;
  115. 			for(i=1;i<x.ss.size();i++)
  116. 			{
  117. 				if(x.ss[i].ss <= prev_y);
  118. 				else
  119. 				{
  120. 					res += (x.ss[i].ff)*(x.ss[i].ss - prev_y);
  121. 				}
  122. 			//	cout << (x.ss[i].ff)*(x.ss[i].ss - prev_y) << ' ';
  123. 				prev_x = x.ss[i].ff;
  124. 				prev_y = x.ss[i].ss;
  125. 			}
  126. 		}
  127. 		cout << res << '\n';
  128. 	}
  129. 	return 0;
  130. }
Success #stdin #stdout 0s 15360KB
comments (?)
stdin
copy 
4
742
gggggttttttttsssssscccciiiipppppppppttttoouuuuuujjzccccwwwwllfffuuujjfffffffnnnnnnnnnicccccuuuuuuuzbbbbbbbvvvvvvvffffffeeeeewwwwwwwgggbdddddlllllllllyaaaaaaauuuuuuuuuaaaaaaaaaeeeeeetddddddddiikbbbbbbmmmmmmmmmooossssssrrrrreevvvvvvvvvfaaaaaaaaannnlllllllllllllyxxxxxxxppxxxxddddddddaaaaaanwwwwjjjjjjjccccccccccxxxxkkkkkkpppbbbaaaaaaaaaawwwwyyyyyyyyywwwwwwwwwwpppppeeeeeeeeettttttttbbbbguuuqqqqyyyyyyyxxxxxxxxxxrrrrrrrfffffffffffuuuuuuuuuukkkkkkkkbbbbbbcccccccvvvvvppppppprrrrrrrrxxxxxxxyyyxzzzzzzzzzwwwwwcccccxxxxxxxxxnnnyyyyylpppppppccccccbbbbbbbqqqqqqqqhhhhhhhhqqqqqddddddddddvvvvvvvvvvxxnnnnnnnttttttttnnnnnnhhhhhhhhhxxxxxxxwwwwwwwwwkkkkzzzzzzzzzzzzzssssxxxxxxxxwwwwwwwuurrrrrrrrnnnnnnnnnnnnnnnnnnhhhhhhhhhaffyyyyyyymmmggggggggcccccccpprrrj
546
eeeeeeeeggggxeeeeeeeeellllllllppppppppppppppppphlllllllllxxxxxxxiiiiiiiiifffffttttmmmmjjjjjjjuuuuuuuuqqqyyyyyyyyyygiiiiiiiiivvvvvvvvvvjjjjjllllllllllllllassshhhhnngggssssssssttttttttttddddddddddkkuuuuuuuuuddddddddykffffffffjjjjjiiiiiiiwwwwwwwwwwcccjjjjjjjjjkkkkkvvvvvnnnnnnnjjjjdddddiiiiivvvnnnnnnnoooooooooddggggggghhhlllllyyyyyyyyyyhhhhhhhiiillllllqqqqqqqqqqppppppppptttaoooooooouuuuugwwwwwwwwwoooovvvvvvvvsmmjjjjjjjjjeeeeeemmmmmmmxxxxddddddddddccccccaaaaggggggggggxxxxxxxxxxiiiivvvvvvaaaaaaaaaqqqpppppppaaaaaaaaggggkkkkkkkkkooootttttttzzzzzzzf
918
dddddduuuuuuuujjjjjjjjjtllllllllllnnnnnnbbbyyyyyooommmmmmmmmmtxxxxxxxffffeeeeuuuuuuooooooooooppppddddddddddlllllllppppppprrrrrrrrrpdddddddddxsssssssssxxxxqqeemmmzzzzzzzzfffffffvvvvvvvvvvttttttttttccccccccllllllllllppppyyuuuuuuuuuiiiiikkkkkkkkkkuuuuuuuuuuuuuoooooooogggffffyyyyimmmmmrrrrrrzzvvvvvvveeeeeeennnnnnddddddaaaaaaaaaaaaaaaaaaawwwbbbbbbrrrrvvvvmmmmmfffffffkkkkkkksssrrrrrrrrriiiiirrrrwwwwwwwwgggggsssssssshhhhhhhaaaaaaaddddddddwwwwwwjjjjjjlllllrrrrrrrrrrrrccccccccccssssskkkkqqrrrryyyyyyvvvvvvvoooooyyyyyyyttttttttlllllllllbbbbbbbbbeeeeeettttttllllllllllkkkkkkkkdddllllpppppppppoooooooooouuuuuuuuuusssssdddmmmmmmmaaaaaafffzzzlllllxxxxxxkkkkkaaaaabbbbbbbbbblllllllllzzzzzzzvvvvvvvfffffffffxxxxxaaaaaaaddddddddggsmmmmmmmmmqqqqqqqqqquuuuqqqqquuuunnnnnnyyyyyyyyeeeezzjjjjjjjjjqnnnnnjjjjjjiiiiiiiqqqqqqqqqqwwwwwwwwwwrrnnbbbdddddzzzzzzooorrrrrrrrrrrrrreeeelllllbbbbbbbbbbccccccccoiiikkkkkkkkrrrrrllllffffzzzzzzzvvvvv
710
wwwwhhhhhssvvvvwwwwwwwwwzzzzzzzzzzdddddfffffffffwwwwwwwwiiiiiiiiiiddddddffffffuuuuuuuuvaaaaaaaaannnuuuuuuuuuooooopppppppptxaaaaaaaqqqqqdooookkkkknnnnnnneeeeeewwwwyyyyyyycccwwwwcccccxxxxxpppptbbbbbbuuuuuuuuuggggggggggaaaaaarrruunnnnnnnnnnrrrrrrrrrrttttttttsssssiiiiiiiiitttttttttaaaaaaaaattttttttoooooooooooooooonnnncccccccciiiiiiiiffffffwwwwwwaaazzzzzzzzssssssddddddddqqqqqqqqqqttttttttttcjjjjjjzzzzzzzzzjjbbbbbbbbbbgggggbbbbbbbbbtttttttttifffffffffuaaaaaaawwwwbbbbbbbbbbbbbbbbhheeeeeeeeevvvvvvrrrrbbbbuuuuuggggwwwwwwwweeeeeeeemmmmmmooooookkkkcccciiiiiiiiiiikkkkkkkkkkxxxxxxxxxxaaaaaaaaammmmmmmcccccccccllaaxxxbbbbbbbbaaaaaaaaaagggggggvvffffffffwdddddddvvvvvvvvveeeeeeeeeelrrrrrrrroooogooooooommmmmyyyyyjaaammm
stdout
copy 
4264
3157
5414
4360
https://ideone.com/pKwvht
language:
C++ (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!