fork(1) download 
  1. #include <iostream>
  2. #include <string>
  3.  
  4. std::string longest_k_substring(std::string s, int k) {
  5. 	int kk, start = 0, end, slen, maxlen = 0, saveStart;
  6. 	int count[256] = {0};
  7. 	slen = s.size();
  8. 	if (k == 0) return "";
  9.  
  10. 	// find the longest prefix that contains <= k different characters
  11. 	for (end = 0, kk = 0; end < slen; ++end) {
  12. 		char c = s[end];
  13. 		if (++count[c] == 1) 	// new character
  14. 		  if (++kk > k) break;
  15. 	}
  16.  
  17. 	while (true) {
  18. 		if (end - start > maxlen) {
  19. 			maxlen = end - start;
  20. 			saveStart = start;
  21. 		}
  22. 		if (end == slen) return s.substr(saveStart, maxlen);
  23.  
  24. 		// increase start until s[start -> end] contains exactly k different characters
  25. 		while (--count[s[start++]]);
  26. 		// increase end until we reach a new character not currently in s[start -> end]
  27. 		while (++end < slen && ++count[s[end]] > 1);
  28. 	}
  29. }
  30.  
  31. int main() {
  32. 	std::string s;
  33. 	int k;
  34.  
  35. 	std::cin >> s >> k;
  36. 	std::cout << longest_k_substring(s, k);
  37.  
  38. 	return 0;
  39. }
Success #stdin #stdout 0s 3476KB
comments (?)
stdin 
aaaaabcdef
3
stdout 
aaaaabc
https://ideone.com/i2JPCq
http://stackoverflow.com/questions/39200952/what-is-the-best-algorithm-to-find-longest-substring-with-constraints
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
secret

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!