fork download
copy 
  1. const fs = require('fs');
  2. const input = fs.readFileSync(0, 'utf8').trim();
  3.  
  4. const countValidByOneFlip = (s) => {
  5.     const n = s.length;
  6.  
  7.     let bal = 0;
  8.     for (const c of s) bal += c === '(' ? 1 : -1;
  9.  
  10.     if (Math.abs(bal) !== 2) return 0;
  11.  
  12.     const pref = new Array(n);
  13.     let x = 0;
  14.     for (let i = 0; i < n; i++) {
  15.         x += s[i] === '(' ? 1 : -1;
  16.         pref[i] = x;
  17.     }
  18.  
  19.     const suffMin = new Array(n + 1);
  20.     suffMin[n] = 1e9;
  21.     x = 0;
  22.     for (let i = n - 1; i >= 0; i--) {
  23.         x += s[i] === '(' ? 1 : -1;
  24.         suffMin[i] = Math.min(x, suffMin[i + 1]);
  25.     }
  26.  
  27.     let target, delta;
  28.     if (bal === -2) {
  29.         target = ')';
  30.         delta = 2;
  31.     } else {
  32.         target = '(';
  33.         delta = -2;
  34.     }
  35.  
  36.     let ans = 0;
  37.  
  38.     for (let i = 0; i < n; i++) {
  39.         if (s[i] !== target) continue;
  40.  
  41.         if (i > 0 && pref[i - 1] < 0) continue;
  42.  
  43.         if (suffMin[i + 1] + delta < 0) continue;
  44.  
  45.         ans++;
  46.     }
  47.  
  48.     return ans;
  49. }
  50.  
  51. console.log(countValidByOneFlip(input));
Success #stdin #stdout 0.04s 40456KB
comments (?)
stdin
copy 
(()))()
stdout
copy 
0
https://ideone.com/xyLHaZ
language:
Node.js (node 20.14)
created:
4 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!