There is a rectangular path for a Train to travel consisting of n rows and m columns. The train will start from one of the grid's cells and it will be given a command in the form of string s consisting of characters L, R, D, U. Find if it is possible to travel the train inside the grid only.
Note: 
If the train is at position (i,j) 
on taking 'L' it goes to (i,j-1),
on taking 'R' it goes to (i,j+1),
on taking 'D' it goes to (i-1,j),
on taking 'U' it goes to (i+1,j).
You just need to tell if it's possible or not, you don't have to tell number of ways in which it is possible.
Example 1:
Input: 
n = 1, m = 1
s = "R"
Output: 0
Explaination: There is only one cell(1,1). So train can only start from (1,1). On taking right(R) train moves to (1,2), which is out of grid.
Therefore there is no cell from where train can start and remain inside the grid after tracing the route. 
Example 2:
Input: 
n = 2, m = 3
s = "LLRU"
Output: 1
Explaination: One possible cell is (1,3)
(1,3) --> (1,2) --> (1,1) --> (1,2) --> (2,2). Thus there is a cell from where if train starts, it remains inside the grid throughout tracing the route.
Your Task:
You do not need to read input or print anything. Your task is to complete the function isPossible() which takes n, m and s as input parameters and returns 1 if there is such a cell for which the train always remains inside the grid. Otherwise returns 0.
Expected Time Complexity: O(|s|)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ n, m ≤ 10^{4}
1 ≤ |s| ≤ 10^{4}

Source: geeksforgeeks | Difficulty: EASY
Tags: Matrices

Data structures

Starter code: #User function Template for python3



class Solution:

    def isPossible(self, n, m, s):

        # code here

Solutions:
class Solution:

	def isPossible(self, n, m, s):
		l = 0
		r = 0
		u = 0
		le = 0
		ri = 0
		do = 0
		for i in s:
			if i == 'L':
				l += 1
			if i == 'R':
				l -= 1
			if i == 'U':
				r += 1
			if i == 'D':
				r -= 1
			u = max(u, r)
			le = max(le, l)
			do = max(do, -r)
			ri = max(-l, ri)
		u += do
		le += ri
		if u > n - 1 or le > m - 1:
			return 0
		return 1


class Solution:

	def isPossible(self, n, m, s):
		i = 0
		j = 0
		menor_i = 999999
		menor_j = 999999
		mayor_i = -999999
		mayor_j = -999999
		for x in s:
			if x == 'L':
				j -= 1
			elif x == 'R':
				j += 1
			elif x == 'D':
				i -= 1
			elif x == 'U':
				i += 1
			else:
				return 0
			if i < menor_i:
				menor_i = i
			if i > mayor_i:
				mayor_i = i
			if j < menor_j:
				menor_j = j
			if j > mayor_j:
				mayor_j = j
			if not (abs(i) <= n - 1 and abs(j) <= m - 1):
				return 0
			if not (abs(mayor_i - menor_i) <= n - 1 and abs(mayor_j - menor_j) <= m - 1):
				return 0
		if abs(i) <= n - 1 and abs(j) <= m - 1:
			return 1
		else:
			return 0


class Solution:

	def isPossible(self, n, m, s):
		x = [0]
		y = [0]
		p = 0
		q = 0
		for i in s:
			if i == 'L':
				q -= 1
			if i == 'R':
				q += 1
			if i == 'U':
				p -= 1
			if i == 'D':
				p += 1
			x.append(p)
			y.append(q)
		if max(x) - min(x) + 1 <= n and max(y) - min(y) + 1 <= m:
			return 1
		return 0


class Solution:

	def isPossible(self, n, m, s):
		(a, b) = (0, 0)
		(rmax, rmin, umax, umin) = (0, 0, 0, 0)
		for i in s:
			if i == 'L':
				a -= 1
			elif i == 'R':
				a += 1
			elif i == 'D':
				b -= 1
			else:
				b += 1
			rmax = max(rmax, a)
			rmin = min(rmin, a)
			umax = max(umax, b)
			umin = min(umin, b)
		if rmax - rmin < m and umax - umin < n:
			return 1
		return 0


class Solution:

	def isPossible(self, n, m, s):
		t_l = 0
		t_r = 0
		t_u = 0
		t_d = 0
		f_lr = 0
		f_ud = 0
		for i in range(len(s)):
			if s[i] == 'L':
				f_lr += 1
			elif s[i] == 'R':
				f_lr -= 1
			elif s[i] == 'U':
				f_ud += 1
			else:
				f_ud -= 1
			if f_lr >= 0:
				t_l = max(t_l, f_lr)
			else:
				t_r = min(t_r, f_lr)
			if f_ud >= 0:
				t_u = max(t_u, f_ud)
			else:
				t_d = min(t_d, f_ud)
		if t_l - t_r < m and t_u - t_d < n:
			return 1
		return 0


class Solution:

	def isPossible(self, n, m, s):
		vertical = 0
		horizontal = 0
		maxH = 0
		minH = 0
		maxV = 0
		minV = 0
		for i in s:
			if i == 'R':
				horizontal += 1
			elif i == 'L':
				horizontal -= 1
			elif i == 'U':
				vertical += 1
			elif i == 'D':
				vertical -= 1
			maxH = max(maxH, horizontal)
			minH = min(minH, horizontal)
			maxV = max(maxV, vertical)
			minV = min(minV, vertical)
			if maxH - minH >= int(m):
				return 0
			if maxV - minV >= int(n):
				return 0
		if maxH - minH >= int(m):
			return 0
		if maxV - minV < int(n):
			return 1
		return 0


class Solution:

	def isPossible(self, n, m, s):
		(maxl, maxr, maxu, maxd, c1, c2) = (0, 0, 0, 0, 0, 0)
		for i in range(len(s)):
			if s[i] == 'L':
				c1 -= 1
			elif s[i] == 'R':
				c1 += 1
			elif s[i] == 'U':
				c2 += 1
			else:
				c2 -= 1
			if c1 >= 0:
				maxr = max(c1, maxr)
			else:
				maxl = min(c1, maxl)
			if c2 >= 0:
				maxu = max(c2, maxu)
			else:
				maxd = min(c2, maxd)
		if maxr + 1 - maxl <= m and maxu + 1 - maxd <= n:
			return 1
		return 0


class Solution:

	def isPossible(self, n, m, s):
		(x, y) = (0, 0)
		(ml, mr, mu, md) = (0, 0, 0, 0)
		for c in s:
			if c == 'L':
				x -= 1
			elif c == 'R':
				x += 1
			elif c == 'U':
				y -= 1
			else:
				y += 1
			ml = min(ml, x)
			mr = max(mr, x)
			mu = min(mu, y)
			md = max(md, y)
		if abs(ml) + mr < m and abs(mu) + md < n:
			return 1
		return 0


class Solution:

	def isPossible(self, n, m, s):
		i = 0
		j = 0
		mic = 0
		mxc = 0
		mir = 0
		mxr = 0
		for x in s:
			if x == 'L':
				j = j - 1
			if x == 'R':
				j = j + 1
			if x == 'D':
				i = i - 1
			if x == 'U':
				i = i + 1
			mic = min(mic, j)
			mxc = max(mxc, j)
			mir = min(mir, i)
			mxr = max(mxr, i)
		if mxr - mir < n and mxc - mic < m:
			return 1
		else:
			return 0


class Solution:

	def isPossible(self, n: int, m: int, s: str) -> int:
		(maxX, maxY, x, y, minX, minY) = (0, 0, 0, 0, 0, 0)
		for i in range(len(s)):
			if s[i] == 'L':
				x = x - 1
			elif s[i] == 'R':
				x = x + 1
			elif s[i] == 'D':
				y = y + 1
			else:
				y = y - 1
			maxX = max(x, maxX)
			maxY = max(y, maxY)
			minX = min(x, minX)
			minY = min(y, minY)
		if maxX + abs(minX) < m and maxY + abs(minY) < n:
			return 1


class Solution:

	def isPossible(self, n, m, s):
		(maxl, maxr, maxu, maxd) = (0, 0, 0, 0)
		(r, c) = (0, 0)
		for i in s:
			if i == 'L':
				c = c - 1
			elif i == 'R':
				c = c + 1
			elif i == 'U':
				r = r + 1
			elif i == 'D':
				r = r - 1
			if c >= 0:
				maxr = max(c, maxr)
			else:
				maxl = min(c, maxl)
			if r >= 0:
				maxu = max(r, maxu)
			else:
				maxd = min(r, maxd)
		if maxr + 1 - maxl <= m and maxu + 1 - maxd <= n:
			return 1
		return 0


class Solution:

	def isPossible(self, n, m, s):
		(top, bottom, left, right) = (0, 0, 0, 0)
		(r, c) = (0, 0)
		for i in s:
			if i == 'L':
				c = c - 1
			if i == 'R':
				c = c + 1
			if i == 'U':
				r = r - 1
			if i == 'D':
				r = r + 1
			top = min(top, r)
			bottom = max(bottom, r)
			left = min(left, c)
			right = max(right, c)
		if bottom + abs(top) < n and right + abs(left) < m:
			return 1
		return 0


class Solution:

	def isPossible(self, n, m, s):
		(minx, miny, maxx, maxy) = (0, 0, 0, 0)
		(dx, dy) = (0, 0)
		for i in s:
			if i == 'L':
				dx -= 1
			elif i == 'R':
				dx += 1
			elif i == 'U':
				dy += 1
			else:
				dy -= 1
			maxx = max(dx, maxx)
			maxy = max(dy, maxy)
			minx = min(dx, minx)
			miny = min(dy, miny)
		if maxx - minx < m and maxy - miny < n:
			return 1
		return 0


class Solution:

	def isPossible(self, n, m, s):
		d = {'L': [0, -1], 'R': [0, 1], 'U': [-1, 0], 'D': [1, 0]}
		(i, j) = (0, 0)
		(x1, x2) = (0, 0)
		(y1, y2) = (0, 0)
		for r in s:
			i += d[r][0]
			j += d[r][1]
			x1 = min(i, x1)
			x2 = max(x2, i)
			y1 = min(y1, j)
			y2 = max(y2, j)
		if x2 - x1 < n and y2 - y1 < m:
			return 1
		return 0


class Solution:

	def isPossible(self, n, m, s):
		(minx, maxx, miny, maxy) = (0, 0, 0, 0)
		(dx, dy) = (0, 0)
		for d in s:
			if d == 'L':
				dx -= 1
			if d == 'R':
				dx += 1
			if d == 'U':
				dy += 1
			if d == 'D':
				dy -= 1
			minx = min(minx, dx)
			maxx = max(maxx, dx)
			miny = min(miny, dy)
			maxy = max(maxy, dy)
		return int(maxx - minx < m and maxy - miny < n)


class Solution:

	def isPossible(self, n, m, s):
		l = r = u = d = 0
		lr = 0
		ud = 0
		for i in s:
			if i == 'L':
				lr -= 1
				if lr < l:
					l = lr
			if i == 'R':
				lr += 1
				if lr > r:
					r = lr
			if i == 'U':
				ud += 1
				if ud > u:
					u = ud
			if i == 'D':
				ud -= 1
				if ud < d:
					d = ud
		if r - l + 1 > m or u - d + 1 > n:
			return 0
		else:
			return 1


class Solution:

	def isPossible(self, n, m, s):
		i1 = 0
		i2 = 0
		j1 = 0
		j2 = 0
		i = 0
		j = 0
		for k in s:
			if k == 'L':
				j -= 1
			elif k == 'R':
				j += 1
			elif k == 'D':
				i -= 1
			elif k == 'U':
				i += 1
			(i1, i2) = (min(i1, i), max(i2, i))
			(j1, j2) = (min(j1, j), max(j2, j))
		if abs(i1 - i2) < n and abs(j1 - j2) < m:
			return 1
		return 0


class Solution:

	def isPossible(self, n, m, s):
		dic = {'L': 0, 'R': 0, 'U': 0, 'D': 0}
		find = {'L': 'R', 'R': 'L', 'U': 'D', 'D': 'U'}
		for el in s:
			dic[el] += 1
			if dic[find[el]] > 0:
				dic[find[el]] -= 1
			if dic['L'] < 0 or dic['R'] < 0 or dic['U'] < 0 or (dic['D'] < 0):
				return 0
			if dic['L'] >= m or dic['R'] >= m or dic['U'] >= n or (dic['D'] >= n):
				return 0
		return 1


class Solution:

	def isPossible(self, n, m, s):
		(imin, imax, jmin, jmax) = (0, 0, 0, 0)
		(i, j) = (0, 0)
		for ch in s:
			if ch == 'L':
				j -= 1
			elif ch == 'R':
				j += 1
			elif ch == 'D':
				i -= 1
			elif ch == 'U':
				i += 1
			(imin, imax) = (min(imin, i), max(imax, i))
			(jmin, jmax) = (min(jmin, j), max(jmax, j))
		if abs(imax - imin) < n and abs(jmax - jmin) < m:
			return 1
		return 0


class Solution:

	def isPossible(self, n, m, s):
		(i, j) = (1, 1)
		(xmn, xmx, ymn, ymx) = (1, 1, 1, 1)
		for ss in s:
			if ss == 'L':
				j -= 1
			elif ss == 'R':
				j += 1
			elif ss == 'D':
				i -= 1
			elif ss == 'U':
				i += 1
			xmx = max(xmx, i)
			xmn = min(xmn, i)
			ymx = max(ymx, j)
			ymn = min(ymn, j)
		return int(abs(ymx - ymn) < m and abs(xmx - xmn) < n)


class Solution:

	def isPossible(self, n, m, s):
		(L, R, T, B) = (0, 0, 0, 0)
		cur = [0, 0]
		for ch in s:
			if ch == 'U':
				cur[0] += 1
				T = max(T, cur[0])
			elif ch == 'D':
				cur[0] -= 1
				B = min(B, cur[0])
			elif ch == 'L':
				cur[1] -= 1
				L = min(L, cur[1])
			elif ch == 'R':
				cur[1] += 1
				R = max(R, cur[1])
		(W, H) = (R - L + 1, T - B + 1)
		return 1 if W <= m and H <= n else 0


class Solution:

	def isPossible(self, n, m, s):
		l = r = t = b = x = y = 0
		for c in s:
			if c == 'L':
				x -= 1
				l = min(l, x)
			elif c == 'R':
				x += 1
				r = max(r, x)
			elif c == 'D':
				y -= 1
				t = min(t, y)
			elif c == 'U':
				y += 1
				b = max(b, y)
		return 1 if r - l <= m - 1 and b - t <= n - 1 else 0


class Solution:

	def isPossible(self, n, m, s):
		up = 0
		down = 0
		left = 0
		right = 0
		for item in s:
			if item == 'L':
				left += 1
				if right > 0:
					right -= 1
			elif item == 'R':
				right += 1
				if left > 0:
					left -= 1
			elif item == 'U':
				up += 1
				if down > 0:
					down -= 1
			else:
				down += 1
				if up > 0:
					up -= 1
			if m - right <= left or n - up <= down:
				return 0
		return 1


class Solution:

	def isPossible(self, n, m, s):
		(i, j) = (0, 0)
		(l, r, u, d) = (0, 0, 0, 0)
		for c in s:
			if c == 'L':
				j -= 1
			elif c == 'R':
				j += 1
			elif c == 'D':
				i -= 1
			else:
				i += 1
			l = min(l, j)
			r = max(r, j)
			d = min(d, i)
			u = max(u, i)
		return 1 if r - l < m and u - d < n else 0


class Solution:

	def isPossible(self, n, m, s):
		(x, y) = (0, 0)
		(l, d, r, u) = (0, 0, 0, 0)
		for i in s:
			if i == 'L':
				x -= 1
			if i == 'R':
				x += 1
			if i == 'D':
				y += 1
			if i == 'U':
				y -= 1
			l = min(l, x)
			r = max(r, x)
			d = max(d, y)
			u = min(u, y)
		N = d - u + 1
		M = r - l + 1
		return int(M <= m and N <= n)


class Solution:

	def isPossible(self, n, m, s):
		x = 0
		y = 0
		maxx = maxy = minx = miny = 0
		for i in s:
			if i == 'L':
				x -= 1
			elif i == 'R':
				x += 1
			elif i == 'U':
				y += 1
			else:
				y -= 1
			maxx = max(x, maxx)
			maxy = max(y, maxy)
			minx = min(x, minx)
			miny = min(y, miny)
			if maxx - minx >= m or maxy - miny >= n:
				return 0
		return 1


class Solution:

	def isPossible(self, n, m, s):
		flag = 0
		hor = 0
		ver = 0
		l_hor = {0}
		l_ver = {0}
		for i in s:
			if i == 'R':
				hor += 1
				l_hor.add(hor)
				if hor >= m:
					return 0
			if i == 'L':
				hor -= 1
				l_hor.add(hor)
				if hor <= -m:
					return 0
			if i == 'U':
				ver -= 1
				l_ver.add(ver)
				if ver <= -n:
					return 0
			if i == 'D':
				ver += 1
				l_ver.add(ver)
				if ver >= n:
					return 0
		if abs(min(l_ver)) + 1 + max(l_ver) > n:
			return 0
		if abs(min(l_hor)) + 1 + max(l_hor) > m:
			return 0
		return 1


class Solution:

	def isPossible(self, n, m, s):
		delta = {'L': (0, -1), 'R': (0, 1), 'U': (-1, 0), 'D': (1, 0)}
		(minx, maxx, miny, maxy) = (0, 0, 0, 0)
		(x, y) = (0, 0)
		for c in s:
			(x, y) = (x + delta[c][0], y + delta[c][1])
			minx = min(minx, x)
			maxx = max(maxx, x)
			miny = min(miny, y)
			maxy = max(maxy, y)
		return 1 if maxx - minx < n and maxy - miny < m else 0


class Solution:

	def isPossible(self, n, m, s):
		x = y = 0
		min_x = min_y = 0
		max_x = max_y = 0
		for c in s:
			if c == 'U':
				x -= 1
				min_x = min(min_x, x)
			elif c == 'D':
				x += 1
				max_x = max(max_x, x)
			elif c == 'L':
				y -= 1
				min_y = min(min_y, y)
			else:
				y += 1
				max_y = max(max_y, y)
		if max_x - min_x < n and max_y - min_y < m:
			return 1
		else:
			return 0


class Solution:

	def isPossible(self, n, m, s):
		x = len(s)
		col = 0
		row = 0
		a = 0
		b = 0
		c = 0
		d = 0
		for i in range(0, x):
			if s[i] == 'L':
				col -= 1
				a = min(col, a)
				b = max(col, b)
			elif s[i] == 'R':
				col += 1
				a = min(col, a)
				b = max(col, b)
			elif s[i] == 'U':
				row -= 1
				c = min(row, c)
				d = max(row, d)
			elif s[i] == 'D':
				row += 1
				c = min(row, c)
				d = max(row, d)
			if b - a > m - 1 or d - c > n - 1:
				return 0
		return 1


from collections import defaultdict

class Solution:

	def isPossible(self, n, m, s):
		max_rel_dists = get_max_rel_dists(s)
		if abs(max_rel_dists['L']) + abs(max_rel_dists['R']) > m - 1:
			return 0
		if abs(max_rel_dists['U']) + abs(max_rel_dists['D']) > n - 1:
			return 0
		return 1

def get_max_rel_dists(s):
	(i, j) = (0, 0)
	max_rel_dists = defaultdict(int)
	for step in s:
		if step == 'L':
			i -= 1
			if i < max_rel_dists[step]:
				max_rel_dists[step] = i
		elif step == 'R':
			i += 1
			if i > max_rel_dists[step]:
				max_rel_dists[step] = i
		if step == 'D':
			j -= 1
			if j < max_rel_dists[step]:
				max_rel_dists[step] = j
		elif step == 'U':
			j += 1
			if j > max_rel_dists[step]:
				max_rel_dists[step] = j
	return max_rel_dists


class Solution:

	def isPossible(self, n, m, s):
		x = y = 0
		max_x = min_x = max_y = min_y = 0
		for i in s:
			if i == 'L':
				y -= 1
			elif i == 'R':
				y += 1
			elif i == 'D':
				x -= 1
			else:
				x += 1
			max_x = max(x, max_x)
			min_x = min(x, min_x)
			max_y = max(y, max_y)
			min_y = min(y, min_y)
			if max_x - min_x >= n or max_y - min_y >= m:
				return 0
		return 1


class Solution:

	def isPossible(self, n, m, s):
		row = n
		col = m
		xmax = 0
		xmin = 0
		ymax = 0
		ymin = 0
		y = 0
		x = 0
		for c in s:
			if c == 'R':
				x += 1
				xmax = max(xmax, x)
			elif c == 'L':
				x -= 1
				xmin = min(xmin, x)
			elif c == 'U':
				y -= 1
				ymin = min(ymin, y)
			elif c == 'D':
				y += 1
				ymax = max(ymax, y)
		if xmax - xmin + 1 > col or ymax - ymin + 1 > row:
			return 0
		return 1


from collections import Counter

class Solution:

	def isPossible(self, n, m, s):
		l = r = u = d = 0
		x = y = 0
		for i in s:
			x += 1 if i == 'R' else -1 if i == 'L' else 0
			if x < 0:
				l = max(l, abs(x))
			else:
				r = max(r, x)
			y += 1 if i == 'U' else -1 if i == 'D' else 0
			if y < 0:
				d = max(d, abs(y))
			else:
				u = max(u, y)
		return 1 if l + r < m and u + d < n else 0


class Solution:

	def isPossible(self, n, m, s):
		lp = 0
		up = 0
		maxlp = 0
		minlp = 0
		maxup = 0
		minup = 0
		for i in range(len(s)):
			if s[i] == 'U':
				up += 1
			if s[i] == 'D':
				up -= 1
			if s[i] == 'L':
				lp += 1
			if s[i] == 'R':
				lp -= 1
			maxlp = max(maxlp, lp)
			minlp = min(minlp, lp)
			maxup = max(maxup, up)
			minup = min(minup, up)
		if maxup + abs(minup) + 1 > n or maxlp + abs(minlp) + 1 > m:
			return 0
		return 1


class Solution:

	def isPossible(self, n, m, s):
		side = 0
		niche = 0
		minSide = 0
		minNiche = 0
		maxSide = 0
		maxNiche = 0
		for x in s:
			if x == 'L':
				side -= 1
			elif x == 'R':
				side += 1
			elif x == 'U':
				niche -= 1
			else:
				niche += 1
			maxNiche = max(niche, maxNiche)
			minSide = min(side, minSide)
			minNiche = min(niche, minNiche)
			maxSide = max(side, maxSide)
		if maxNiche + abs(minNiche) > n - 1 or maxSide + abs(minSide) > m - 1:
			return 0
		return 1


class Solution:

	def isPossible(self, n, m, s):
		i = j = max_j = min_j = max_i = min_i = 0
		for cmd in s:
			if cmd == 'L':
				j -= 1
			elif cmd == 'R':
				j += 1
			elif cmd == 'D':
				i -= 1
			elif cmd == 'U':
				i += 1
			if max_j < j:
				max_j = j
			elif min_j > j:
				min_j = j
			elif min_i > i:
				min_i = i
			elif max_i < i:
				max_i = i
		return 1 if abs(max_i - min_i) < n and abs(min_j - max_j) < m else 0


class Solution:

	def isPossible(self, n, m, s):
		col_min = 0
		col_max = 0
		row_min = 0
		row_max = 0
		row = 0
		column = 0
		for i in s:
			if i == 'L':
				column -= 1
				col_min = min(col_min, column)
			if i == 'R':
				column += 1
				col_max = max(col_max, column)
			if i == 'U':
				row -= 1
				row_min = min(row_min, row)
			if i == 'D':
				row += 1
				row_max = max(row_max, row)
		if col_max - col_min < m and row_max - row_min < n:
			return 1
		return 0


class Grid:

	def __init__(self, n, m):
		self.n = n
		self.m = m
		self.curr = [1, 1]

	def is_valid(self):
		return 1 <= self.curr[0] <= self.m and 1 <= self.curr[1] <= self.n

	def move(self, s: str):
		if s == 'L':
			change = [0, -1]
		elif s == 'R':
			change = [0, 1]
		elif s == 'U':
			change = [1, 0]
		elif s == 'D':
			change = [-1, 0]
		self.curr[0] += change[0]
		self.curr[1] += change[1]
		return self.is_valid()

class Solution:

	def isPossible(self, n, m, s):
		(x, y) = (0, 0)
		(ml, mr, mu, md) = (0, 0, 0, 0)
		for c in s:
			if c == 'L':
				x -= 1
			elif c == 'R':
				x += 1
			elif c == 'U':
				y -= 1
			else:
				y += 1
			ml = min(ml, x)
			mr = max(mr, x)
			mu = min(mu, y)
			md = max(md, y)
		if abs(ml) + mr < m and abs(mu) + md < n:
			return 1
		return 0


class Solution:

	def isPossible(self, n, m, s):
		i = j = 0
		min_i = min_j = max_i = max_j = 0
		for c in s:
			if c == 'L':
				j -= 1
			elif c == 'R':
				j += 1
			elif c == 'U':
				i += 1
			elif c == 'D':
				i -= 1
			min_i = min(i, min_i)
			min_j = min(j, min_j)
			max_i = max(i, max_i)
			max_j = max(j, max_j)
		return int(max_i - min_i < n and max_j - min_j < m)