fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <climits>
  5. using namespace std;
  6.  
  7. int main() {
  8.     string s;
  9.     cin >> s;
  10.     int n = s.size();
  11.  
  12.     // difference of '(' - ')' from the beginning to position i
  13.     vector<int> prefix(n + 1, 0);
  14.  
  15.     for (int i = 0; i < n; ++i) {
  16.         prefix[i + 1] = prefix[i] + (s[i] == '(' ? 1 : -1);
  17.     }
  18.  
  19.     // minimum value of prefix from the beginning to position i
  20.     vector<int> minPrefix(n + 1, 0);
  21.     minPrefix[0] = prefix[0];
  22.     for (int i = 1; i <= n; ++i) {
  23.         minPrefix[i] = min(minPrefix[i - 1], prefix[i]);
  24.     }
  25.  
  26.     // minimum value of prefix from position i to the end
  27.     vector<int> minSuffix(n + 2, INT_MAX);
  28.     minSuffix[n + 1] = INT_MAX;
  29.     for (int i = n; i >= 0; --i) {
  30.         minSuffix[i] = min(minSuffix[i + 1], prefix[i]); 
  31.     }
  32.  
  33.     int ans = 0;
  34.     for (int i = 0; i < n; ++i) {
  35.         // flip the parenthesis at position i
  36.         int delta = (s[i] == '(' ? -2 : 2); 
  37.         int total = prefix[n] + delta;
  38.  
  39.         // The part before position i: prefix must always be >= 0
  40.         if (minPrefix[i] < 0) continue;
  41.  
  42.         // The part after: after flipping, the minimum value must be >= 0
  43.         int after_min = minSuffix[i + 1] + delta;
  44.         if (after_min < 0) continue;
  45.  
  46.         // The final total must be 0
  47.         if (total == 0) ans++;
  48.     }
  49.  
  50.     cout << ans << endl;
  51.     return 0;
  52. }
  53.  
Success #stdin #stdout 0s 5312KB
comments (?)
stdin
copy 
()(())))
stdout
copy 
4
https://ideone.com/EiJpkh
language:
C++14 (gcc 8.3)
created:
10 hours 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!