leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0395.cpp (981B)

      1 class Solution {
      2   public:
      3     int longestSubstring(const string &s, int k) const {
      4         const int n = size(s);
      5         static int count[26];
      6         int res = 0, maxUnique = 0;
      7 
      8         memset(count, 0x00, sizeof(count));
      9         for (const char c : s)
     10             maxUnique += !count[c - 'a']++;
     11 
     12         for (int l = 1; l <= maxUnique; l++) {
     13             memset(count, 0x00, sizeof(count));
     14             int i = 0, j = 0, unique = 0, least = 0;
     15             while (j < n) {
     16                 if (unique <= l) {
     17                     unique += !count[s[j] - 'a']++;
     18                     least += count[s[j] - 'a'] == k;
     19                     j++;
     20                 } else {
     21                     least -= count[s[i] - 'a'] == k;
     22                     unique -= !--count[s[i] - 'a'];
     23                     i++;
     24                 }
     25 
     26                 if (unique == l && least == l) {
     27                     res = max(res, j - i);
     28                 }
     29             }
     30         }
     31 
     32         return res;
     33     }
     34 };