fork download
copy 
  1. /**
  2.  * Problem:
  3.  * Count how many single-character flips (either '(' -> ')' or ')' -> '(')
  4.  * would result in a valid parentheses string.
  5.  *
  6.  * A string is valid if:
  7.  * 1. Total balance is 0 (same number of '(' and ')')
  8.  * 2. At any prefix, the number of ')' does not exceed '(' (i.e., prefix balance ≥ 0)
  9.  *
  10.  * Strategy:
  11.  * - Use prefixBalance to track balance at each index
  12.  * - Use prefixMin to ensure the prefix remains valid
  13.  * - Use suffixMinOffset to ensure suffix remains valid after a flip
  14.  *
  15.  * @param {string} s - Input string of parentheses
  16.  * @returns {number} Number of valid single-character flips
  17.  */
  18. function countValidParenthesesFixes(s) {
  19.     const n = s.length;
  20.  
  21.     // Step 1: Calculate prefix balance at every index
  22.     const balanceAt = Array(n).fill(0); // balanceAt[i] = net balance at s[0..i]
  23.     for (let i = 0; i < n; i++) {
  24.         const delta = s[i] === '(' ? 1 : -1;
  25.         balanceAt[i] = (i > 0 ? balanceAt[i - 1] : 0) + delta;
  26.     }
  27.  
  28.     const totalBalance = balanceAt[n - 1]; // Final balance of full string
  29.     // Early return: impossible to fix if balance ≠ ±2
  30.     if (Math.abs(totalBalance) !== 2) return 0;
  31.  
  32.     // Step 2: Compute prefix minimum balance at each point
  33.     const minPrefixBalance = Array(n).fill(0);
  34.     minPrefixBalance[0] = balanceAt[0];
  35.     for (let i = 1; i < n; i++) {
  36.         minPrefixBalance[i] = Math.min(minPrefixBalance[i - 1], balanceAt[i]);
  37.     }
  38.  
  39.     /**
  40.      * Step 3: Compute suffixMinOffset[i]
  41.      * It indicates how deep (min balance drop) the suffix from index i goes.
  42.      * Used to detect if suffix becomes invalid after a flip.
  43.      */
  44.     const suffixMinOffset = Array(n).fill(0);
  45.     suffixMinOffset[n - 1] = 0;
  46.     for (let i = n - 2; i >= 0; i--) {
  47.         const diff = balanceAt[i + 1] - balanceAt[i];
  48.         suffixMinOffset[i] = Math.min(0, suffixMinOffset[i + 1] + diff);
  49.     }
  50.  
  51.     // Step 4: Try flipping each character
  52.     let validFlipCount = 0;
  53.  
  54.     for (let i = 0; i < n; i++) {
  55.         const flipDelta = s[i] === '(' ? -2 : 2;
  56.  
  57.         // Rule 1: total balance after flip must be 0
  58.         if (totalBalance + flipDelta !== 0) continue;
  59.  
  60.         // Rule 2: prefix before flip must be valid
  61.         if (i > 0 && minPrefixBalance[i - 1] < 0) continue;
  62.  
  63.         // Rule 3: suffix after flip must stay valid
  64.         const balanceBefore = i > 0 ? balanceAt[i - 1] : 0;
  65.         const newBalanceAtFlip = balanceBefore + (s[i] === '(' ? -1 : 1);
  66.         const newSuffixMin = newBalanceAtFlip + suffixMinOffset[i];
  67.  
  68.         if (newSuffixMin >= 0) {
  69.             validFlipCount++;
  70.         }
  71.     }
  72.  
  73.     return validFlipCount;
  74. }
  75.  
  76. let input = '';
  77. process.stdin.on('data', function (chunk) {
  78.     input += chunk;
  79. });
  80.  
  81. process.stdin.on('end', function () {
  82.     const lines = input.trim().split('\n');
  83.     for (const line of lines) {
  84.         console.log(countValidParenthesesFixes(line.trim()));
  85.     }
  86. });
  87.  
Success #stdin #stdout 0.07s 43472KB
comments (?)
stdin
copy 
()(())))
()(((()()())
(((((((((((()))))))))))(((((((((())))))))))(((((((((()))))))))))(((((((((()))))))))))(
(()(()(()(()))(()(()(()(()(()(()(()(()(()(()(()(()(()(()(()(()(()(()(()(()(()(()(((()))))
stdout
copy 
4
5
0
0
https://ideone.com/9Eizdk
Ewoosoft - Vu Van Nhan - Prob Typo
language:
Node.js (node 20.14)
created:
6 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!