我写了个$O(n^2)$的暴力拿了50，教练要我们将这份代码优化成$O(n)$过掉这题，请问如何优化？

#include<iostream>
#include<stack>
using namespace std;
int n,cnt,ans,T;
string s;
stack<char>st;
int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		cin>>s;
		for(int l=0;l<n;l++)
		{
			while(!st.empty())
			{
				st.pop();
			}	
			cnt=0;	
			st.push(s[l]);
			for(int r=l+1;r<n;r++)
			{
				if(st.empty())
				{
					cnt++;				
					st.push(s[r]);
					continue;
				}
				if(st.top()==s[r])
				{
					st.pop();
					if(st.empty()&&r==n-1)
					{
						cnt++;
					}				
				}
				else
				{
					st.push(s[r]);
				}
			}
			ans+=cnt;
		}
		printf("%d",ans);		
	}
	return 0;
}