1073C - Vasya and Robot - CodeForces Solution

#include<bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(), x.end()
#define nl '\n'
#define int long long
#define pii pair<int, int>
//#define ll long long
#define mod 1000000007  // 998244353  1000000007
using namespace std;
const int N = 2e5 + 5;
int a[N][26];
int n;
int x, y;
bool ok(int mid)
{
	int r = a[mid - 1]['R' - 'A'], u = a[mid - 1]['U' - 'A'], l = a[mid - 1]['L' - 'A'], d = a[mid - 1]['D' - 'A'];
	int tr = a[n - 1]['R' - 'A'], tu = a[n - 1]['U' - 'A'], tl = a[n - 1]['L' - 'A'], td = a[n - 1]['D' - 'A'];
	int tx = tr - r - (tl - l), ty = tu - u - (td - d);
	if((abs(x - tx) + abs(y - ty)) <= mid) 
	{
		int k = mid - abs(x - tx) - abs(y - ty);
		if(k % 2 == 0) return true;
	}
	for(int i = mid; i < n; i++)
	{
		r = a[i]['R' - 'A'] - a[i - mid]['R' - 'A'],
		u = a[i]['U' - 'A'] - a[i - mid]['U' - 'A'],
		l = a[i]['L' - 'A'] - a[i - mid]['L' - 'A'],
		d = a[i]['D' - 'A'] - a[i - mid]['D' - 'A'];
		tx = tr - r - (tl - l), ty = tu - u - (td - d);
		if((abs(x - tx) + abs(y - ty)) <= mid)
		{
			int k = mid - abs(x - tx) - abs(y - ty);
			if(k % 2 == 0) return true;
			continue;
//			cout << "r: " << r << " l: " << l << " d: " << d << " u: " << u << nl;
//			cout << mid << " tx: " << tx << " ty: " << ty << nl;
//			cout << (abs(x - tx) + abs(y - ty)) << nl;
			
		}
	}
	return false;
}
void solve()
{
	cin >> n;
	string s;
	cin >> s;
	cin >> x >> y;
	if(abs(x) > n or abs(y) > n)
	{
		cout << -1 << nl;
		return;
	}
	for(int i = 0; i < n; i++)
	{
		a[i][s[i] - 'A']++;
		if(i != 0)
		{
			a[i]['R' - 'A'] += a[i - 1]['R' - 'A'];
			a[i]['L' - 'A'] += a[i - 1]['L' - 'A'];
			a[i]['D' - 'A'] += a[i - 1]['D' - 'A'];
			a[i]['U' - 'A'] += a[i - 1]['U' - 'A'];
		}
	}
	int tx = (a[n - 1]['R' - 'A'] - a[n - 1]['L' - 'A']), ty = (a[n - 1]['U' - 'A'] - a[n - 1]['D' - 'A']);
	if(tx == x and ty == y)
	{
		cout << 0 << nl;
		return;
	}
	int l = 1, r = n;
	int ans = 1e9;
	while(l <= r)
	{
		int mid = (l + r)/2;
		if(ok(mid))
		{
			ans = mid;
			r = mid - 1;
		}
		else
		{
			l = mid + 1;
		}
	}
	if(ans == 1e9)
	{
		cout << -1 << nl;
	}
	else
	{
		cout << ans << nl;
	}
}
signed main()
{
	ios_base::sync_with_stdio(false), cin.tie(nullptr);
	int t = 1;
//	cin >> t;
	while(t--)
	{
		solve();
	}
}