# O(N) time and space (using stack)

• I implemented using two stacks, one is for ‘(‘ and ‘’ count and other for keeping ‘’.

1. For every ‘(‘, push stack-1 with char and count of stack-2.
2. For every ‘*’, push to stack-2
3. For every ‘)’, pop from stack-1 if it is not empty, else pop from stack-2. If both stacks are empty return false.
4. Finally, pop everything from stack-1 and return false if starcount is less than stack-2 count.
``````public class CharandStarCount
{
public char ch;
public int startCount;
public CharandStarCount(char ch, int cnt)
{
this.ch = ch;
this.startCount = cnt;
}
}
public class Solution {
bool removeFromStack (Stack<CharandStarCount> par, Stack<char> star)
{
if (par.Count > 0)
{
par.Pop();
return true;
}

if (star.Count > 0)
{
star.Pop();
return true;
}
return false;
}

public bool CheckValidString(string s) {
if (s == String.Empty || s == null)
return true;
Stack<CharandStarCount> pstack = new Stack<CharandStarCount>();
Stack<char> sstack = new Stack<char>();
foreach(char ch in s)
{
switch (ch)
{
case '(' :
CharandStarCount temp = new CharandStarCount(ch,sstack.Count);
pstack.Push(temp);
break;
case '*':
sstack.Push(ch);
break;
case ')':
if (!removeFromStack(pstack,sstack))
return false;
break;
}
}

int starcount =0;
while ( pstack.Count > 0 )
{
CharandStarCount temp = pstack.Pop();

if (temp.startCount < sstack.Count)
{
sstack.Pop();

} else {
return false;
}
}

return true;
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.