Advertisement
2696. Minimum String Length After Removing Substrings
EasyView on LeetCode
Time: O(n)
Space: O(n)
Approach
Stack simulation; pop 'A' when 'B' arrives, pop 'C' when 'D' arrives.
2696.cs
C#
// Approach: Stack simulation; pop 'A' when 'B' arrives, pop 'C' when 'D' arrives.
// Time: O(n) Space: O(n)
public class Solution
{
public int MinLength(string s)
{
Stack<char> st = new Stack<char>();
foreach (char c in s)
{
if (c == 'B' && isMatched(st, 'A'))
st.Pop();
else if (c == 'D' && isMatched(st, 'C'))
st.Pop();
else
st.Push(c);
}
return st.Count;
}
private bool isMatched(Stack<char> st, char c)
{
return st.Count > 0 && st.Peek() == c;
}
}Advertisement
Was this solution helpful?