fork download
copy 
  1.  
  2. import java.io.BufferedReader;
  3. import java.io.IOException;
  4. import java.io.InputStreamReader;
  5. import java.util.StringTokenizer;
  6.  
  7. public class Main {
  8.  
  9. 	static int p1 = 0;
  10. 	static int p2 = -1;
  11. 	static int p3 = -1;
  12. 	static int u;
  13. 	static int[] fBefP = new int[26];
  14. 	static int[] ftot = new int[26];
  15. 	static int ans = 0;
  16. 	static int tempU = 0;
  17. 	static int tempUBeforeP2 = 0;
  18. 	static String s;
  19. 	public static void main(String[] args){
  20. 		MyScanner sc = new MyScanner();
  21. 		s = sc.nextLine();
  22. 		boolean[] a = new boolean[26];
  23. 		int U = 0;
  24. 		for(int i = 0;i<s.length();i++){
  25. 			int c = cal(s.charAt(i));
  26. 			if(a[c]==false){
  27. 				U++;
  28. 				a[c]= true;
  29. 			}
  30. 		}
  31. 		System.out.println(U);
  32. 		int n=1;
  33. 		char c = s.charAt(0);
  34. 		for(int i = 1;i<s.length();i++){
  35.  
  36. 			if(s.charAt(i)==c){
  37. 				n++;
  38. 			}
  39. 			else{
  40. 				ans += n*(n+1)/2;
  41. 				n = 1;
  42. 				c = s.charAt(i);
  43. 			}
  44. 		}
  45. 		ans += n*(n+1)/2;
  46. 		System.out.println(ans);
  47. 		for(u=2;u<=U;u++){
  48. 			p1 = 0;
  49. 			p2 = -1;
  50. 			p3 = -1;
  51. 			tempU= 0;
  52. 			ans = 0;
  53. 			ftot = new int[26];
  54. 			fBefP = new int[26];
  55. 			tempUBeforeP2 = 0;
  56. 			while(tempU<u){
  57.  
  58. 				p2++;
  59. 				if(p2==s.length())
  60. 					break;
  61. 				int cp2 = cal(s.charAt(p2));
  62. 				if(ftot[cp2]==0){
  63. 					tempU++;
  64. 					tempUBeforeP2++;
  65. 				}
  66. 				fBefP[cp2]++;
  67. 				ftot[cp2]++;
  68. 			}
  69. 			p3 = p2;
  70.  
  71. 			while(tempU==u){
  72.  
  73. 				p3++;
  74. 				if(p3==s.length()){
  75. 					tempU++;
  76. 					break;
  77. 				}
  78. 				int cp3 = cal(s.charAt(p3));
  79. 				if(ftot[cp3]==0){
  80. 					tempU++;
  81.  
  82. 				}
  83. 				ftot[cp3]++;
  84.  
  85. 			}
  86.  
  87. 		    boolean ch1 = addSubs();
  88. 			boolean w = true;
  89.  
  90.  
  91.  
  92. 			while(w){
  93.  
  94. 				if(ch1){
  95. 				while(movP2()){
  96.  
  97. 					boolean check = addSubs();
  98.  
  99. 					if(check==false){
  100.  
  101. 						break;
  102. 					}
  103.  
  104. 				}
  105. 				}
  106.  
  107. 				w = movP3();
  108. 				ch1 = true;
  109.  
  110. 			}
  111. 			System.out.println(ans);
  112. 		}
  113. 	}
  114.  
  115. 	public static boolean addSubs(){
  116.  
  117. 		while(tempU>u && tempUBeforeP2==u){
  118.  
  119. 			ans += p3-p2;
  120. 			int cp1 = cal(s.charAt(p1));
  121.  
  122. 			if(fBefP[cp1]==1){
  123. 				tempUBeforeP2--;
  124. 			}
  125.  
  126. 			if(ftot[cp1]==1){
  127.  
  128. 				tempU--;
  129. 			}
  130.  
  131. 			fBefP[cp1]--;
  132. 			ftot[cp1]--;
  133. 			p1++;
  134. 		}
  135. 		if(tempU==u){
  136. 			return false;
  137. 		}
  138. 		else{
  139. 			return true;
  140. 		}
  141.  
  142. 	}
  143.  
  144. 	public static boolean movP2(){
  145. 		int req = 0;
  146. 		while(req<1){
  147. 			p2++;
  148.  
  149. 			int cp2 =cal(s.charAt(p2));
  150.  
  151. 			if(fBefP[cp2]==0){
  152. 				req++;
  153. 				tempUBeforeP2++;
  154. 			}
  155. 			fBefP[cp2]++;
  156. 			if(p2>=p3-1 && req<1)
  157. 				return false;
  158.  
  159. 		}
  160. 		return true;
  161. 	}
  162.  
  163. 	public static boolean movP3(){
  164. 		if(p3==s.length())
  165. 			return false;
  166. 		else{
  167.  
  168. 			while(tempU==u){
  169. 				p3++;
  170. 				if(p3==s.length()){
  171. 					tempU++;
  172. 					break;
  173. 				}
  174. 				int cp3 = cal(s.charAt(p3));
  175. 				if(ftot[cp3]==0){
  176. 					tempU++;
  177. 				}
  178. 				ftot[cp3]++;
  179. 			}
  180. 			return true;
  181. 		}
  182. 	}
  183.  
  184. 	public static int cal(char c){
  185. 		return ((int)c-97);
  186. 	}
  187.  
  188. }
  189.  
  190.  
  191. class MyScanner {
  192. 	   BufferedReader br;
  193. 	   StringTokenizer st;
  194.  
  195. 	   public MyScanner() {
  196. 	      br = new BufferedReader(new InputStreamReader(System.in));
  197. 	   }
  198.  
  199. 	   String next() {
  200. 	      while (st == null || !st.hasMoreElements()) {
  201. 	         try {
  202. 	            st = new StringTokenizer(br.readLine());
  203. 	         } catch (IOException e) {
  204. 	            e.printStackTrace();
  205. 	         }
  206. 	      }
  207. 	      return st.nextToken();
  208. 	   }
  209.  
  210. 	   int nextInt() {
  211. 	      return Integer.parseInt(next());
  212. 	   }
  213.  
  214. 	   long nextLong() {
  215. 	      return Long.parseLong(next());
  216. 	   }
  217.  
  218. 	   double nextDouble() {
  219. 	      return Double.parseDouble(next());
  220. 	   }
  221.  
  222. 	   String nextLine(){
  223. 	      String str = "";
  224. 	      try {
  225. 	         str = br.readLine();
  226. 	      } catch (IOException e) {
  227. 	         e.printStackTrace();
  228. 	      }
  229. 	      return str;
  230. 	   } 
  231. 	}
  232.  
Success #stdin #stdout 0.1s 320320KB
comments (?)
stdin
copy 
aaa
stdout
copy 
1
6
https://ideone.com/fVParM
language:
Java (HotSpot 12)
created:
9 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!