fork download
copy 
  1. #include <vector>
  2. #include <limits>
  3. #include <string>
  4. #include <iostream>
  5. #include <array>
  6. #include <cassert>
  7.  
  8. class Solution {
  9.   std::array<unsigned short, 256> has;
  10. public:
  11.   int lengthOfLongestSubstring(std::string s) {
  12.     std::fill(has.begin(), has.end(), std::numeric_limits<unsigned short>::max());
  13.  
  14.     int max = 0, current = 0;
  15.     int i = 0, j = 0;
  16.  
  17.     while ( i + max < s.length() && j < s.length() ) {
  18.       char c = s[j];
  19.       if ( has[c] == std::numeric_limits<unsigned short>::max() ) {
  20.         has[c] = j++;
  21.         if ( ++current > max ) {
  22. 	  max = current;
  23. 	}
  24.       } else {
  25. 	auto b = has[c] + 1;
  26. 	do {
  27. 	  has[s[i++]] = std::numeric_limits<unsigned short>::max();
  28. 	} while ( i < b );
  29. 	// current = j - i + 1;
  30.         has[c] = j++;
  31. 	current = j - i;
  32.       }
  33.     }
  34.  
  35.     return max;
  36.   }
  37. };
  38.  
  39. int main()
  40. {
  41.   Solution s;
  42.   auto n = s.lengthOfLongestSubstring("aab");
  43.   std::cout << "n = " << n << std::endl;
  44.   assert(n == 2);
  45.   n = s.lengthOfLongestSubstring("pwwkew");
  46.   std::cout << "n = " << n << std::endl;
  47.   assert(n == 3);
  48.   n = s.lengthOfLongestSubstring("tmmzuxt");
  49.   std::cout << "n = " << n << std::endl;
  50.   assert(n == 5);
  51.   n = s.lengthOfLongestSubstring("dvdf");
  52.   std::cout << "n = " << n << std::endl;
  53.   assert(n == 3);
  54.   n = s.lengthOfLongestSubstring("ckilbkd");
  55.   std::cout << "n = " << n << std::endl;
  56.   assert(n == 5);
  57.  
  58.   return 0;
  59. }
  60.  
Success #stdin #stdout 0s 5604KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
n = 2
n = 3
n = 5
n = 3
n = 5
https://ideone.com/RtRcXD
language:
C++ (gcc 8.3)
created:
3 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!