fork download 
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. #include <sstream>
  5. #include <algorithm>
  6.  
  7. // Check if the input is valid: only '(' and ')', and no extra characters
  8. bool checkInput(const std::string& s) {
  9.     if (s.empty() || s.size() > 100000) 
  10.     	return false;
  11.  
  12.     std::istringstream ss(s);
  13.     std::string token, remain;
  14.     if (!(ss >> token) || (ss >> remain)) return false;
  15.  
  16.     for (char c : s) {
  17.         if (c != '(' && c != ')') return false;
  18.     }
  19.  
  20.     return true;
  21. }
  22.  
  23. // Count the number of ways to change exactly one parenthesis to make the string valid
  24. int countValidCorrections(const std::string& s) {
  25.     int n = s.size();
  26.  
  27.     std::vector<int> total(n);     // total[i]: cumulative sum from s[0] to s[i], with '(' = +1, ')' = -1
  28.     std::vector<int> minLeft(n);   // minLeft[i]: minimum value of total[0..i]
  29.     std::vector<int> minRight(n);  // minRight[i]: minimum value of total[i..n-1]
  30.  
  31.     total[0] = (s[0] == '(' ? 1 : -1);
  32.     minLeft[0] = total[0];
  33.     for (int i = 1; i < n; ++i) {
  34.         int value = (s[i] == '(' ? 1 : -1);
  35.         total[i] = total[i - 1] + value;
  36.         minLeft[i] = std::min(minLeft[i - 1], total[i]);
  37.     }
  38.  
  39.     minRight[n - 1] = total[n - 1];
  40.     for (int i = n - 2; i >= 0; --i) {
  41.         minRight[i] = std::min(total[i], minRight[i + 1]);
  42.     }
  43.  
  44.     if (std::abs(total[n - 1]) != 2) 
  45.         return 0;
  46.  
  47.     bool isTotalPlus2 = (total[n - 1] == 2);
  48.     char changeChar = isTotalPlus2 ? '(' : ')';
  49.     int flip = isTotalPlus2 ? -2 : 2;
  50.  
  51.     int result = 0;
  52.     for (int i = 0; i < n; ++i) {
  53.         if (s[i] == changeChar) {
  54.             bool isValidLeft = (i == 0 || minLeft[i - 1] >= 0);
  55.             bool isValidRight = (minRight[i] + flip >= 0);
  56.             if (isValidLeft && isValidRight) 
  57.                 ++result;
  58.         }
  59.     }
  60.  
  61.     return result;
  62. }
  63.  
  64. int main() {
  65.     std::string s;
  66.     std::cin >> s;
  67.  
  68.     if (!checkInput(s)) {
  69.         std::cout << "Invalid input: The string must contain only '(' and ')' and its length must be between 1 and 100000.\n";
  70.         return 1;
  71.     }
  72.  
  73.     std::cout << countValidCorrections(s) << std::endl;
  74.     return 0;
  75. }
  76.  
Success #stdin #stdout 0.01s 5328KB
comments (?)
stdin 
()(())))
stdout 
4
https://ideone.com/9zAH6n
language:
C++14 (gcc 8.3)
created:
7 days 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!