Competitive Programming Solutions

1462B - Last Years Substring

15 Dec 2020 — Tags: implementation,strings — URL

There are three successful cases for a string $s$:

  1. $s$ = 2020
  2. 2020 is a prefix of $s$
  3. 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;
}

Related posts