fork download
copy 
  1. process.stdin.resume();
  2. process.stdin.setEncoding('utf8');
  3.  
  4. // your code goes here
  5. function solve() {
  6.   const input = require('fs').readFileSync('/dev/stdin', 'utf8').trim();
  7.   const s = input;
  8.   const n = s.length;
  9.  
  10.   if (n % 2 === 1) {
  11.     console.log(0);
  12.     return;
  13.   }
  14.  
  15.   let openCount = 0;
  16.   for (let i = 0; i < n; i++) {
  17.     if (s[i] === '(') openCount++;
  18.   }
  19.  
  20.   const target = n / 2;
  21.  
  22.   if (Math.abs(openCount - target) !== 1) {
  23.     console.log(0);
  24.     return;
  25.   }
  26.  
  27.   const balance = new Array(n + 1).fill(0);
  28.   for (let i = 0; i < n; i++) {
  29.     balance[i + 1] = balance[i] + (s[i] === '(' ? 1 : -1);
  30.   }
  31.  
  32.   const minBalanceFromStart = new Array(n + 1).fill(0);
  33.   minBalanceFromStart[0] = balance[0];
  34.   for (let i = 1; i <= n; i++) {
  35.     minBalanceFromStart[i] = Math.min(balance[i], minBalanceFromStart[i - 1]);
  36.   }
  37.  
  38.   const minBalanceToEnd = new Array(n + 2).fill(Infinity);
  39.   minBalanceToEnd[n] = balance[n];
  40.   for (let i = n - 1; i >= 0; i--) {
  41.     minBalanceToEnd[i] = Math.min(balance[i], minBalanceToEnd[i + 1]);
  42.   }
  43.  
  44.   let validFlips = 0;
  45.  
  46.   if (openCount === target + 1) {
  47.     for (let i = 0; i < n; i++) {
  48.       if (s[i] === '(') {
  49.         if (minBalanceFromStart[i] >= 0 && minBalanceToEnd[i + 1] >= 2) {
  50.           validFlips++;
  51.         }
  52.       }
  53.     }
  54.   }
  55.  
  56.   if (openCount === target - 1) {
  57.     for (let i = 0; i < n; i++) {
  58.       if (s[i] === ')') {
  59.         if (minBalanceFromStart[i] >= 0 && minBalanceToEnd[i + 1] >= -2) {
  60.           validFlips++;
  61.         }
  62.       }
  63.     }
  64.   }
  65.  
  66.   console.log(validFlips);
  67. }
  68.  
  69. solve();
Success #stdin #stdout 0.07s 43076KB
comments (?)
stdin
copy 
()(())))
stdout
copy 
4
https://ideone.com/zbk1Bq
language:
Node.js (node 20.14)
created:
2 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!