fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. const int N = 10;
  9.  
  10. struct Node {
  11.     int next[N];
  12.     bool terminal;
  13.     Node() {
  14.         for (int i = 0; i < N; i++) {
  15.             next[i] = -1;
  16.         }
  17.         terminal = false;
  18.     }
  19. };
  20.  
  21. vector<Node> trie;
  22.  
  23. void add_string(const string& s) {
  24.     int v = 0;
  25.     for (char c : s) {
  26.         int idx = c - 'a';
  27.         if (trie[v].next[idx] == -1) {
  28.             trie.push_back(Node());
  29.             trie[v].next[idx] = trie.size() - 1;
  30.         }
  31.         v = trie[v].next[idx];
  32.     }
  33.     trie[v].terminal = true;
  34. }
  35.  
  36. string find_min_missing_string(const string& s) {
  37.     trie.push_back(Node());
  38.     for (int i = 0; i < s.size(); i++) {
  39.         string substr = s.substr(i, 1);
  40.         add_string(substr);
  41.     }
  42.  
  43.     string min_missing = "";
  44.     for (int len = 1; len <= s.size(); len++) {
  45.         for (int i = 0; i < (1 << (len * N)); i++) {
  46.             string substr;
  47.             for (int j = 0; j < len; j++) {
  48.                 int idx = (i >> (j * N)) & ((1 << N) - 1);
  49.                 substr += 'a' + idx;
  50.             }
  51.             int v = 0;
  52.             bool found = false;
  53.             for (char c : substr) {
  54.                 int idx = c - 'a';
  55.                 if (trie[v].next[idx] == -1) {
  56.                     found = true;
  57.                     break;
  58.                 }
  59.                 v = trie[v].next[idx];
  60.             }
  61.             if (!found) {
  62.                 if (min_missing.empty() || substr < min_missing) {
  63.                     min_missing = substr;
  64.                 }
  65.             }
  66.         }
  67.     }
  68.  
  69.     return min_missing;
  70. }
  71.  
  72. int main() {
  73.     int n;
  74.     string s;
  75.     cin >> n >> s;
  76.  
  77.     string min_missing = find_min_missing_string(s);
  78.     cout << min_missing << endl;
  79.  
  80.     return 0;
  81. }
  82.  
Success #stdin #stdout 0s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 

	

		
	 
	
	
			

					
			
			
			
			
			
			
			
			

			
			
			
		

	
		
		

			

			                        







			
			

				

	
					
					 https://ideone.com/7mN8lE
					
					
					
					
					

												

												
						
						

					

					
					
					

						
language:

						
C++ (gcc 8.3)

					

					

						
created:
								
						
12 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!