Buggy python submission (verdict: Time Limit Exceeded):
def main():
    from collections import namedtuple

    Q = namedtuple('Q', 'char drc')

    def binary_search(ng, ok):
        def is_ok(mid):
            """落下するならTrue"""
            for q_ in qs:
                if s[mid] == q_.char:
                    mid += q_.drc
                    if mid < 0 or mid >= n:
                        return True
            return False

        while abs(ng - ok) > 1:
            mid = (ng + ok) // 2
            if is_ok(mid):
                ok = mid
            else:
                ng = mid
        return ok

    n, q = map(int, input().split())
    s = input()

    qs = []
    for _ in range(q):
        t, d = input().split()
        d = -1 if (d == 'L') else 1
        qs.append(Q(char=t, drc=d))
        # char:指定マス文字,英大文字
        # drc:方向,L=-1,R=1

    mid = n // 2
    left = binary_search(ng=mid + 1, ok=-1)  # okを返すので、最大mid
    right = binary_search(ng=mid, ok=n)  # okを返すので、最小mid+1
    # ok=落下する境目（落下側）
    # oolxxxroo -> r-1-l=6-1-2=3=xの個数
    # 012345678

    print(right - 1 - left)


if __name__ == '__main__':
    main()


Fixed submission:
"""https://atcoder.jp/contests/exawizards2019/submissions/4769434
左右どちらから消滅するか確認が必要だと気づかされた"""


def get_pos(index):
    """初期位置indexのロボットのクエリ後の配置を返す
    is_whick_sideの返り値として返す"""
    iws = -1 if index == -1 else 1 if index == N else 0
    if iws != 0:
        return iws
    for t, d in e:
        if t == s[index]:
            if d == 'R':
                index += 1
            else:
                index -= 1
        iws = -1 if index == -1 else 1 if index == N else 0
        if iws != 0:
            return iws
    return 0


N, Q = map(int, input().split())
s = input()

e = [input().split() for _ in range(Q)]
# t: 文字 <- siと比較
# d: 'L', 'R'

# right
left = -1
right = N
while right - left > 1:
    mid = (left + right) // 2
    if get_pos(mid) == 1:
        # 右消滅
        right = mid
    else:
        left = mid
ar = right
# 右消滅開始位置

# left
left = -1
right = N
while right - left > 1:
    mid = (left + right) // 2
    if get_pos(mid) == -1:
        left = mid
    else:
        right = mid
al = left
# 左消滅開始位置
# (al, ar) = 残存区間

print((ar - 1) - (al + 1) + 1)

Buggy python submission (verdict: Time Limit Exceeded):
DEBUG = False


def get_pos(index):
    """初期位置indexのロボットのクエリ後の配置を返す
    is_whick_sideの返り値として返す"""
    if DEBUG: print()
    iws = -1 if index == -1 else 1 if index == N else 0
    if iws != 0:
        if DEBUG: print(iws)
        return iws
    for t, d in e:
        if DEBUG: print(index, s[index], t, d, end='')
        if t == s[index]:
            if d == 'R':
                index += 1
            else:
                index -= 1
        if DEBUG: print('->', index, s[index] if 0 <= index < N else '==Removed')
        iws = -1 if index == -1 else 1 if index == N else 0
        if iws != 0:
            if DEBUG: print(iws)
            return iws
    if DEBUG: print(0)
    return 0


N, Q = map(int, input().split())
s = input()

e = [input().split() for _ in range(Q)]
# t: 文字 <- siと比較
# d: 'L', 'R'

# right
left = -1
right = N
while right - left > 1:
    mid = (left + right) // 2
    if get_pos(mid) == 1:
        # 右消滅
        right = mid
    else:
        left = mid
    if DEBUG: print('lr', left, right)
ar = right
if DEBUG: print('right', ar)
# 右消滅開始位置

# left
left = -1
right = N
while right - left > 1:
    mid = (left + right) // 2
    if get_pos(mid) == -1:
        left = mid
    else:
        right = mid
    if DEBUG: print('lr', left, right)
al = left
if DEBUG: print('left', al)
# 左消滅開始位置
# (al, ar) = 残存区間

print((ar - 1) - (al + 1) + 1)


Fixed submission:
"""https://atcoder.jp/contests/exawizards2019/submissions/4769434
左右どちらから消滅するか確認が必要だと気づかされた"""


def get_pos(index):
    """初期位置indexのロボットのクエリ後の配置を返す
    is_whick_sideの返り値として返す"""
    iws = -1 if index == -1 else 1 if index == N else 0
    if iws != 0:
        return iws
    for t, d in e:
        if t == s[index]:
            if d == 'R':
                index += 1
            else:
                index -= 1
        iws = -1 if index == -1 else 1 if index == N else 0
        if iws != 0:
            return iws
    return 0


N, Q = map(int, input().split())
s = input()

e = [input().split() for _ in range(Q)]
# t: 文字 <- siと比較
# d: 'L', 'R'

# right
left = -1
right = N
while right - left > 1:
    mid = (left + right) // 2
    if get_pos(mid) == 1:
        # 右消滅
        right = mid
    else:
        left = mid
ar = right
# 右消滅開始位置

# left
left = -1
right = N
while right - left > 1:
    mid = (left + right) // 2
    if get_pos(mid) == -1:
        left = mid
    else:
        right = mid
al = left
# 左消滅開始位置
# (al, ar) = 残存区間

print((ar - 1) - (al + 1) + 1)

Buggy python submission (verdict: Time Limit Exceeded):
DEBUG = False


def get_pos(index):
    """初期位置indexのロボットのクエリ後の配置を返す
    is_whick_sideの返り値として返す"""
    if DEBUG: print()
    iws = is_whick_side(index)
    if iws != 0:
        if DEBUG: print(iws)
        return iws
    for t, d in e:
        if DEBUG: print(index, s[index], t, d, end='')
        if t == s[index]:
            if d == 'R':
                index += 1
            else:
                index -= 1
        if DEBUG: print('->', index, s[index] if 0 <= index < N else '==Removed')
        iws = is_whick_side(index)
        if iws != 0:
            if DEBUG: print(iws)
            return iws
    if DEBUG: print(0)
    return 0


def is_whick_side(index):
    if index == -1:
        return -1
        # 左消滅
    elif index == N:
        return 1
        # 右消滅
    else:
        return 0
        # 非消滅
    # 二分探索中に左右どちらから消滅したか把握しておかないと
    # midの初期値が消滅だった場合に
    # indexの-1側,N側どちら側に次の探索範囲を設ければよいのか判断できない


N, Q = map(int, input().split())
s = input()

e = [input().split() for _ in range(Q)]
# t: 文字 <- siと比較
# d: 'L', 'R'

# right
left = -1
right = N
while right - left > 1:
    mid = (left + right) // 2
    if get_pos(mid) == 1:
        # 右消滅
        right = mid
    else:
        left = mid
    if DEBUG: print('lr', left, right)
ar = right
if DEBUG: print('right', ar)
# 右消滅開始位置

# left
left = -1
right = N
while right - left > 1:
    mid = (left + right) // 2
    if get_pos(mid) == -1:
        left = mid
    else:
        right = mid
    if DEBUG: print('lr', left, right)
al = left
if DEBUG: print('left', al)
# 左消滅開始位置
# (al, ar) = 残存区間

print((ar - 1) - (al + 1) + 1)


Fixed submission:
"""https://atcoder.jp/contests/exawizards2019/submissions/4769434
左右どちらから消滅するか確認が必要だと気づかされた"""


def get_pos(index):
    """初期位置indexのロボットのクエリ後の配置を返す
    is_whick_sideの返り値として返す"""
    iws = -1 if index == -1 else 1 if index == N else 0
    if iws != 0:
        return iws
    for t, d in e:
        if t == s[index]:
            if d == 'R':
                index += 1
            else:
                index -= 1
        iws = -1 if index == -1 else 1 if index == N else 0
        if iws != 0:
            return iws
    return 0


N, Q = map(int, input().split())
s = input()

e = [input().split() for _ in range(Q)]
# t: 文字 <- siと比較
# d: 'L', 'R'

# right
left = -1
right = N
while right - left > 1:
    mid = (left + right) // 2
    if get_pos(mid) == 1:
        # 右消滅
        right = mid
    else:
        left = mid
ar = right
# 右消滅開始位置

# left
left = -1
right = N
while right - left > 1:
    mid = (left + right) // 2
    if get_pos(mid) == -1:
        left = mid
    else:
        right = mid
al = left
# 左消滅開始位置
# (al, ar) = 残存区間

print((ar - 1) - (al + 1) + 1)