O(N^2)의 복잡도가 나오기 때문에 해결하기 힘듭니다.

스택을 활용한 O(N*36)의 풀이가 있습니다.

regex로는 아예 불가능 한가요? stack으로 풀긴 했는데 regex로도 풀어보고 싶어서..

시간복잡도에 대해 공부해보세요. 이 문제에서는 regex를 쓰는게 naive하게 스트링을 검색하는 제곱 풀이보다 나을게 없어보입니다. 물론 제곱 풀이는 TLE이구요.

ABBBBBBBBBBBBBBBBBBBBBBBB, AAAAAAAAAAAABBBBBBBBBBBBB 같은 입력을 생각해 보시면 될 것 같습니다.

매칭해야 하는 문자열을 'AB' 라 했을 때 모두 한 번의 조사에 한 가지 경우만 나오면서 엄청나게 많은 횟수를 매칭하는 것을 요구하는 케이스들입니다.

한 번 문자열을 찾아 지우면 나머지 문자열들을 모두 왼쪽으로 옮겨 빈자리를 채우게 되므로 이동하는 연산을 어마어마하게 많이 해야 하며, 두 번째 케이스에서는 'AB' 하나를 찾기 위해 문자열을 최소 절반은 탐색해야 하는 상황이 발생합니다.

이를 고려했을 때 정규 표현식(regex)로 케이스를 일일이 찾아 지우는 것은 비효율적인 방법이 될 수 있습니다. 사실 regex도 문자열 매칭을 좀 편하게 만들어 줄 뿐이지 시간복잡도는 replace() 같은 기본 값 변경 메소드와 크게 다르지 않습니다.