fork download
copy 
  1.  
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. int calculateValidSegments(string codeSequence) {
  6.     int n = codeSequence.size();
  7.     long long ans = 0;
  8.  
  9.     vector<int> freq(7, 0);
  10.     int distinct = 0;
  11.     int maxFreq = 0;
  12.  
  13.     int r = 0;
  14.  
  15.     for (int l = 0; l < n; l++) {
  16.         while (r < n) {
  17.             int idx = codeSequence[r] - 'a';
  18.             freq[idx]++;
  19.  
  20.             if (freq[idx] == 1)
  21.                 distinct++;
  22.  
  23.             maxFreq = max(maxFreq, freq[idx]);
  24.  
  25.             // Invalid → rollback and stop
  26.             if (maxFreq > distinct) {
  27.                 freq[idx]--;
  28.                 if (freq[idx] == 0)
  29.                     distinct--;
  30.                 break;
  31.             }
  32.  
  33.             r++;
  34.         }
  35.  
  36.         // All substrings [l..l], [l..l+1] ... [l..r-1]
  37.         ans += (r - l);
  38.  
  39.         // Remove left character
  40.         int leftIdx = codeSequence[l] - 'a';
  41.         freq[leftIdx]--;
  42.         if (freq[leftIdx] == 0)
  43.             distinct--;
  44.  
  45.  
  46.         // Recompute maxFreq (only 7 chars → cheap)
  47.         maxFreq = 0;
  48.         for (int i = 0; i < 7; i++)
  49.             maxFreq = max(maxFreq, freq[i]);
  50.     }
  51.  
  52.     return ans;
  53. }
  54.  
  55.  
  56. int main() {
  57.     cout<<calculateValidSegments("aaccd");
  58.     return 0;
  59. }
  60.  
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
11
https://ideone.com/qnHa3o
language:
C++ (gcc 8.3)
created:
1 day 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!