Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Find valid string after removing minimum number of invalid parentheses - mock interview as interviewee - 8:00 PM - Oct. 4, 2020
// Given a string s of '(' , ')' and lowercase English characters. Remove the minimum number of parenthesis to make the parentheses in the string valid.
//
// s = "a)b(c)d"
// res = "ab(c)d"
// VALID - isValid
// ( -> INDEX ) -> valid string ->
// openPara
// ((( ->
// ()()(
// (()()
// -- -
// bfs -> VALID BRUTE FORCE
// ONCE - SHOULD BE Minimum number
// BFS ->
// ()() -> ok
// (() -> remove one, index 0 or 1 -> find valid (), remove open
// ()(( -> remove two,
// check not valid
// 0 )(( -> queue
// 1 (((
// 2 ()(
// 3 ()( ->
// ------------------------
// 0 )(( -> queue
// 1 (((
// 2 () ->
// 3 ()( ->
()()))
--
)()))
- --
remove minimum number parenthese - remove all valid
find one -> make it quick and short ->
// ----------------------
string FindMinimumNumberToRemove(string s)
{
if(s == null || s.Length == 0)
return 0;
if(isValid(s))
{
return 0;
}
// queue - BFS - save index position of open or close parentheses
// index - int[], size - 2, index position - second - 0, close 1
// Tuple<string, int>
var queue = new Queue<Tuple<string, int>>();
queue.Enqueue(new Tuple<string,int>(s, 0));
int index = 1;
// (a)b)
// ()((
// -
// ((((((( ->
// O(m * m * N * N) -
// m is how many strings (count of parenthese), n is size of string - 4
// space -> queue O(m! * n) - m is count of parent chars in string
// m + m*(m-1) + m(m-1)(m-2) + ... + m!
// m* m!= (m+1)! loosely upper bound
// 10 -> 10*9 -> 10*9*8
// 10 -> 10: 9 -> 90: 8
while(queue.Count > 0)
{
// BFS - every string will be check - O(m) count of parenthese < N
var count = queue.Count;
for(int i = 0; i < count; i++)
{
//(a)b)
var current = queue.Dequeue();
var item1 = current.Item1;
var item2 = current.Item2;
// O(N * N)
for(int j = item2; j < current.Length; j++) // (
{
var c = current[j];
var isPare = c == '(' || c== ')';
if(isPare)
{
var tmp = current.RemoveAt(j);
if(isValid(tmp)
{
return tmp;
}
else
{ // one char shorter
queue.Enqueue(new Tuple<string, int>(tmp, j));
}
}
}
}
index++;
}
}
// O(N) - N length of S
private bool isValid(string s)
{
if(s == null || s.Length == 0)
return true;
int openCount = 0;
for(int i = 0; i < s.Length; i++)
{
var c = s[i];
if(c == '(')
{
openCount++;
}
else if(c == ')')
{
if(openCount == 0)
{
return false;
}
openCount--;
}
}
return openCount == 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.