fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <unordered_map>
  5. #include <algorithm>
  6.  
  7. typedef std::vector<int> vector;
  8. typedef std::string string;
  9. typedef std::unordered_map<char, int> unordered_map;
  10. typedef unordered_map::iterator map_iter;
  11.  
  12. int longestSubstring(const string & str, int k) {
  13.  
  14. 	if (str.length() == 0 || k < 0) {
  15. 		return { 0 };
  16. 	}
  17.  
  18. 	int size = str.length();
  19. 	int start = 0;
  20. 	int astart = 0;
  21. 	unordered_map map;
  22. 	int maxSize = 0;
  23. 	int count = 0;
  24. 	char c;
  25.  
  26. 	for (int i = 0; i < size; i++) {
  27. 		c = str[i];
  28.  
  29. 		if (map.find(c) != map.end()) {
  30. 			map[c]++;
  31. 		}
  32. 		else {
  33. 			map.insert({ c, 1 });
  34. 		}
  35.  
  36. 		while (map.size() > k) {
  37. 			c = str[start];
  38. 			count = map[c];
  39. 			if (count > 1) {
  40. 				map[c]--;
  41. 			}
  42. 			else {
  43. 				map.erase(c);
  44. 			}
  45. 			start++;
  46. 		}
  47.  
  48. 		if (map.size() == k) 
  49. 			if (i - start + 1 > maxSize) {
  50. 				maxSize = i - start + 1;
  51. 				astart = start;
  52. 			}
  53. 	}
  54.  
  55. 	std::cout << astart << std::endl;
  56. 	return maxSize;
  57. }
  58.  
  59. int main()
  60. {
  61. 	int ds = longestSubstring("aabacbebebe", 3);
  62. 	std::cout << ds << std::endl;
  63.  
  64. }
  65.  
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
4
7
https://ideone.com/ASfmju
language:
C++ (gcc 8.3)
created:
6 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!