Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8
import sys
import numpy as np

input = sys.stdin.readline

N, Q = map(int, input().split())
S = input().strip()
td_list = [input().split() for _ in range(Q)]
dest = [-2] * (N+1)

def sim(i): # i番目のゴーレムの最終結果を得る
  idx = i
  if dest[i] != -2:
    return dest[i]
  for td in td_list:
    if idx == -1:
      dest[i] = -1
      return -1
    elif idx == N:
      dest[i] = N
      return N
    elif td[0] == S[idx]:
      if td[1] == "L":
        idx -= 1
      else:
        idx += 1
  dest[i] = idx
  return idx


# 左側の境界を探索
idx = N // 2
lb = 0

while True:
  if idx == N-1: # すべて左に出た
    lb = N-1
    break
  l = sim(idx)
  r = sim(idx+1)
  if l == -1 and r != -1: # 境界がみつかった
    lb = idx
    break
  if l == -1:
    idx = (idx + N) // 2
  else:
    idx = idx // 2

# 右側の境界を探索
idx = N // 2
rb = 0

while True:
  if idx == 0: # すべて右に出た
    rb = 0
    break
  l = sim(idx)
  r = sim(idx+1)
  if l != N and r == N: # 境界が見つかった
    rb = idx
    break
  if l != N:
    idx = (idx + N) // 2 
  else:
    idx = idx // 2

print(rb - lb)


Fixed submission:
# coding: utf-8
import sys

input = sys.stdin.readline

N, Q = map(int, input().split())
S = input().strip()
td_list = [input().split() for _ in range(Q)]
dest = [-2] * (N+1)

def sim(i): # i番目のゴーレムの最終結果を得る
  idx = i
  if dest[i] != -2:
    return dest[i]
  for td in td_list:
    if idx == -1:
      dest[i] = -1
      return -1
    elif idx == N:
      dest[i] = N
      return N
    elif td[0] == S[idx]:
      if td[1] == "L":
        idx -= 1
      else:
        idx += 1
  dest[i] = idx
  return idx


# 左側の境界を探索
left, right = -1, N

while right - left != 1:
  mid = (left + right) // 2
  if sim(mid) == -1:
    left = mid
  else:
    right = mid

lb = right

# 右側の境界を探索
left, right = -1, N

while left+1 < right:
  mid = (left + right) // 2
  if sim(mid) == N:
    right = mid
  else:
    left = mid

rb = left

print(rb - lb + 1)

Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8
import sys
import numpy as np

input = sys.stdin.readline

N, Q = map(int, input().split())
S = input().strip()
td_list = [input().split() for _ in range(Q)]

def sim(idx): # i番目のゴーレムの最終結果を得る
  for td in td_list:
    if idx == -1:
      return -1
    elif idx == N:
      return N
    elif td[0] == S[idx]:
      if td[1] == "L":
        idx -= 1
      else:
        idx += 1
  return idx


# 左側の境界を探索
idx = N // 2
lb = 0

while True:
  if idx == N-1: # すべて左に出た
    lb = N-1
    break
  l = sim(idx)
  r = sim(idx+1)
  if l == -1 and r != -1: # 境界がみつかった
    lb = idx
    break
  if l == -1:
    idx = (idx + N) // 2
  else:
    idx = idx // 2

# 右側の境界を探索
idx = N // 2
rb = 0

while True:
  if idx == 0: # すべて右に出た
    rb = 0
    break
  l = sim(idx)
  r = sim(idx+1)
  if l != N and r == N: # 境界が見つかった
    rb = idx
    break
  if l != N:
    idx = (idx + N) // 2 
  else:
    idx = idx // 2

print(rb - lb)

Fixed submission:
# coding: utf-8
import sys

input = sys.stdin.readline

N, Q = map(int, input().split())
S = input().strip()
td_list = [input().split() for _ in range(Q)]
dest = [-2] * (N+1)

def sim(i): # i番目のゴーレムの最終結果を得る
  idx = i
  if dest[i] != -2:
    return dest[i]
  for td in td_list:
    if idx == -1:
      dest[i] = -1
      return -1
    elif idx == N:
      dest[i] = N
      return N
    elif td[0] == S[idx]:
      if td[1] == "L":
        idx -= 1
      else:
        idx += 1
  dest[i] = idx
  return idx


# 左側の境界を探索
left, right = -1, N

while right - left != 1:
  mid = (left + right) // 2
  if sim(mid) == -1:
    left = mid
  else:
    right = mid

lb = right

# 右側の境界を探索
left, right = -1, N

while left+1 < right:
  mid = (left + right) // 2
  if sim(mid) == N:
    right = mid
  else:
    left = mid

rb = left

print(rb - lb + 1)

Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8
import sys
import numpy as np

input = sys.stdin.readline

N, Q = map(int, input().split())
S = input().strip()

tile = {} # 文字マップ
now = np.array([1] * (N+2))

for s in "ABCDEFGHIJKLMNOPQRSTUVWXYZ":
  tile.setdefault(s, [])

for i in range(len(S)):
  tile[S[i]].append(i+1)

for i in range(Q):
  t, d = input().split()
  old = now[tile[t]]
  if d == "L":
    now[(np.array(tile[t])-1).tolist()] += old
    now[tile[t]] -= old
  else:
    now[(np.array(tile[t])+1).tolist()] += old
    now[tile[t]] -= old

#print(now)
print(sum(now) - now[0] - now[-1])

Fixed submission:
# coding: utf-8
import sys

input = sys.stdin.readline

N, Q = map(int, input().split())
S = input().strip()
td_list = [input().split() for _ in range(Q)]
dest = [-2] * (N+1)

def sim(i): # i番目のゴーレムの最終結果を得る
  idx = i
  if dest[i] != -2:
    return dest[i]
  for td in td_list:
    if idx == -1:
      dest[i] = -1
      return -1
    elif idx == N:
      dest[i] = N
      return N
    elif td[0] == S[idx]:
      if td[1] == "L":
        idx -= 1
      else:
        idx += 1
  dest[i] = idx
  return idx


# 左側の境界を探索
left, right = -1, N

while right - left != 1:
  mid = (left + right) // 2
  if sim(mid) == -1:
    left = mid
  else:
    right = mid

lb = right

# 右側の境界を探索
left, right = -1, N

while left+1 < right:
  mid = (left + right) // 2
  if sim(mid) == N:
    right = mid
  else:
    left = mid

rb = left

print(rb - lb + 1)

Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8
import sys

input = sys.stdin.readline

N, Q = map(int, input().split())
S = input().strip()

tile = {} # 文字マップ
now = [1] * N

for s in "ABCDEFGHIJKLMNOPQRSTUVWXYZ":
  tile.setdefault(s, [])

for i in range(len(S)):
  tile[S[i]].append(i)

for i in range(Q):
  t, d = input().split()
  if d == "L":
    for j in tile[t]:
      if j != 0:
        now[j-1] += now[j]
      now[j] = 0
  else:
    for j in tile[t]:
      if j != N-1:
        now[j+1] += now[j]
      now[j] = 0

print(sum(now))

Fixed submission:
# coding: utf-8
import sys

input = sys.stdin.readline

N, Q = map(int, input().split())
S = input().strip()
td_list = [input().split() for _ in range(Q)]
dest = [-2] * (N+1)

def sim(i): # i番目のゴーレムの最終結果を得る
  idx = i
  if dest[i] != -2:
    return dest[i]
  for td in td_list:
    if idx == -1:
      dest[i] = -1
      return -1
    elif idx == N:
      dest[i] = N
      return N
    elif td[0] == S[idx]:
      if td[1] == "L":
        idx -= 1
      else:
        idx += 1
  dest[i] = idx
  return idx


# 左側の境界を探索
left, right = -1, N

while right - left != 1:
  mid = (left + right) // 2
  if sim(mid) == -1:
    left = mid
  else:
    right = mid

lb = right

# 右側の境界を探索
left, right = -1, N

while left+1 < right:
  mid = (left + right) // 2
  if sim(mid) == N:
    right = mid
  else:
    left = mid

rb = left

print(rb - lb + 1)

Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8

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

tile = {} # 文字マップ
now = [1] * N

for s in "ABCDEFGHIJKLMNOPQRSTUVWXYZ":
  tile.setdefault(s, [])

for i in range(len(S)):
  tile[S[i]].append(i)

for i in range(Q):
  t, d = input().split()
  if d == "L":
    for j in tile[t]:
      if j != 0:
        now[j-1] += now[j]
      now[j] = 0
  else:
    for j in tile[t]:
      if j != N-1:
        now[j+1] += now[j]
      now[j] = 0

print(sum(now))

Fixed submission:
# coding: utf-8
import sys

input = sys.stdin.readline

N, Q = map(int, input().split())
S = input().strip()
td_list = [input().split() for _ in range(Q)]
dest = [-2] * (N+1)

def sim(i): # i番目のゴーレムの最終結果を得る
  idx = i
  if dest[i] != -2:
    return dest[i]
  for td in td_list:
    if idx == -1:
      dest[i] = -1
      return -1
    elif idx == N:
      dest[i] = N
      return N
    elif td[0] == S[idx]:
      if td[1] == "L":
        idx -= 1
      else:
        idx += 1
  dest[i] = idx
  return idx


# 左側の境界を探索
left, right = -1, N

while right - left != 1:
  mid = (left + right) // 2
  if sim(mid) == -1:
    left = mid
  else:
    right = mid

lb = right

# 右側の境界を探索
left, right = -1, N

while left+1 < right:
  mid = (left + right) // 2
  if sim(mid) == N:
    right = mid
  else:
    left = mid

rb = left

print(rb - lb + 1)