2116. Check if a Parentheses String Can Be Valid
Approach
Two greedy passes (L→R and R→L) tracking range of possible open-bracket counts.
Key Techniques
String problems range from simple character counting to complex pattern matching. Common approaches include two pointers, sliding window, prefix hashing, and the KMP algorithm. In C#, strings are immutable — use StringBuilder for efficient concatenation inside loops.
Greedy algorithms make locally optimal choices at each step, hoping to reach a global optimum. Greedy works when a problem has the "greedy choice property" and "optimal substructure". Common applications: interval scheduling, activity selection, Huffman coding, and jump game.
Stacks support LIFO (last-in, first-out) operations in O(1). Key patterns: balanced parentheses, next greater element (monotonic stack), function call simulation, and undo/redo. A monotonic stack maintains a strictly increasing or decreasing order to answer range queries efficiently.
// Approach: Two greedy passes (L→R and R→L) tracking range of possible open-bracket counts.
// Time: O(n) Space: O(1)
public class Solution
{
public bool CanBeValid(string s, string locked)
{
if (s.Length % 2 == 1)
return false;
return Check(s, locked, true) && Check(ReverseString(s), ReverseString(locked), false);
}
private bool Check(string s, string locked, bool isForward)
{
int changeable = 0;
int l = 0;
int r = 0;
for (int i = 0; i < s.Length; ++i)
{
char c = s[i];
char lockChar = locked[i];
if (lockChar == '0')
++changeable;
else if (c == '(')
++l;
else // c == ')'
++r;
if (isForward && changeable + l - r < 0)
return false;
if (!isForward && changeable + r - l < 0)
return false;
}
return true;
}
private string ReverseString(string s)
{
char[] charArray = s.ToCharArray();
Array.Reverse(charArray);
return new string(charArray);
}
}