1462B - Last Years Substring
15 Dec 2020 — Tags: implementation,strings — URLThere are three successful cases for a string $s$:
- $s$ =
2020
2020
is a prefix of $s$2020
is a suffix of $s$
To see if $s$ matches one of these cases, compute the longest common prefix
between $s$ and 2020
and the longest common suffix between $s$ and 2020
.
If the sum of those answers is greater or equal than $4$, then it means that
I can combine them together (removing the excess in the middle) and get
$2020$.
Time complexity: $O(n)$
Memory complexity: $O(n)$
Click to show code.
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
bool solve(string s)
{
int n = (int)(s).size();
string sub = "2020";
if (s == sub)
return true;
int pre = 0, suf = 0;
while (pre < 4 and s[pre] == sub[pre])
++pre;
while (suf < 4 and s[n - suf - 1] == sub[4 - suf - 1])
++suf;
return pre + suf >= 4;
}
int main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
int t;
cin >> t;
while (t--)
{
int n;
string s;
cin >> n >> s;
cout << (solve(s) ? "YES" : "NO") << endl;
}
return 0;
}