fork download
copy 
  1. #include <iostream>
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. int main() {
  6. 	int n ; cin>>n;
  7. 	string s; cin>>s;
  8. 	vector<int>prefix(n);
  9. 	int cost = n ; 
  10.  
  11. 	for(int i = 0 ; i<n;i++){
  12. 		if(i==0){
  13. 			if(s[i]=='b'){
  14. 			prefix[i]=1;
  15. 		   }
  16. 		   else{
  17. 		   	prefix[i]=0;
  18. 		   }
  19.  
  20. 		}
  21. 		else{
  22. 			if(s[i]=='b'){
  23. 			prefix[i]=prefix[i-1]+1;
  24. 		}
  25. 	    else{
  26. 			prefix[i]=prefix[i-1];
  27. 		}
  28.  
  29. 		}
  30.  
  31. 	}
  32. 	for(int i = 0 ; i<n;i++){
  33. 		cout<<prefix[i]<<" ";
  34. 	}
  35. 	vector<int>suffix(n);
  36.  
  37. 	for(int i = n-1;i>=0;i--){
  38. 		if(i==n-1){
  39. 			if(s[i]=='a'){
  40. 			suffix[i]=1;
  41. 		   }
  42. 		   else{
  43. 		   	suffix[i]=0;
  44. 		   }
  45.  
  46. 		}
  47. 		else{
  48. 			if(s[i]=='a'){
  49. 			suffix[i]=suffix[i+1]+1;
  50. 		}
  51. 		else{
  52. 			suffix[i]=suffix[i+1];
  53. 		}
  54.  
  55. 		}
  56.  
  57. 	}
  58. 	cout<<"\n";
  59. 	for(int i = 0 ; i<n;i++){
  60. 		cout<<suffix[i]<<" ";
  61. 	}
  62. 	for(int i = 0 ; i<n;i++){
  63. 		if(i==0){
  64. 			cost = suffix[i];
  65. 		}
  66. 		else if(i==n-1){
  67. 			cost = min(cost , prefix[i]);
  68. 		}
  69. 		else{
  70. 			cost = min(cost , prefix[i]+suffix[i+1]);
  71. 		}
  72.  
  73. 	}
  74. 	vector<int>prefix2(n);
  75. 	for(int i = 0 ; i<n;i++){
  76. 		if(i==0){
  77. 			if(s[i]=='a'){
  78. 			prefix2[i]=1;
  79. 		   }
  80. 		   else{
  81. 		   	prefix2[i]=0;
  82. 		   }
  83.  
  84. 		}
  85. 		else{
  86. 			if(s[i]=='a'){
  87. 			prefix2[i]=prefix2[i-1]+1;
  88. 		}
  89. 	    else{
  90. 			prefix2[i]=prefix2[i-1];
  91. 		}
  92.  
  93. 		}
  94.  
  95. 	}
  96. 	vector<int>suffix2(n);
  97.  
  98. 	for(int i = n-1;i>=0;i--){
  99. 		if(i==n-1){
  100. 			if(s[i]=='b'){
  101. 			suffix2[i]=1;
  102. 		   }
  103. 		   else{
  104. 		   	suffix2[i]=0;
  105. 		   }
  106.  
  107. 		}
  108. 		else{
  109. 			if(s[i]=='b'){
  110. 			suffix2[i]=suffix2[i+1]+1;
  111. 		}
  112. 		else{
  113. 			suffix2[i]=suffix2[i+1];
  114. 		}
  115.  
  116. 		}
  117.  
  118. 	}
  119. 	for(int i = 0 ; i<n;i++){
  120. 		if(i==0){
  121. 			cost = min(cost,suffix2[i]);
  122. 		}
  123. 		else if(i==n-1){
  124. 			cost = min(cost , prefix2[i]);
  125. 		}
  126. 		else{
  127. 			cost = min(cost , prefix2[i]+suffix2[i+1]);
  128. 		}
  129.  
  130. 	}
  131.  
  132. 	cout<<"\n"<<cost;
  133. 	return 0;
  134.  
  135. }
Success #stdin #stdout 0.01s 5308KB
comments (?)
stdin
copy 
5
bbbab
stdout
copy 
1 2 3 3 4 
1 1 1 1 0 
1
https://ideone.com/zvBG7u
language:
C++ (gcc 8.3)
created:
3 days 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!