正の整数 \(n\) について、 \((\) \(n\) 個の ( \(+\) xx \(+\) \(n\) 個の ) \()\) となっている部分文字列は \(n\) 回置換すれば xx となります。これを文字列全体で行えば公式解法での 標準形 となります。

\(n\) 回の置換は行いたくないので、正規表現で一括置換することを考えます。ただし、正規表現で左右それぞれに同じ個数の ( と ) とするのは難しいです。

(\(+)xx(\)+) として左右の括弧をできるかぎり長くマッチさせたうえで、括弧の個数を調節させることができればよいです。

これは正規表現の置換に関数を渡せる環境(多くの高級な環境で可能でしょう)ならば可能です。

import re


def eval(m: re.Match[str]) -> str:
    l = len(m.group(1))
    r = len(m.group(2))
    if l > r:
        return ("(" * (l - r)) + "xx"
    elif l < r:
        return "xx" + (")" * (r - l))
    return "xx"


def replace(a: str):
    return re.sub(r"(\(+)xx(\)+)", eval, a)


for _ in range(int(input())):
    a = replace(input())
    b = replace(input())
    if a == b:
        print("Yes")
    else:
        print("No")

提出: https://atcoder.jp/contests/abc454/submissions/78734942