USACO 2021 January Contest Bronze Division - Uddered but not Herd

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

Keep track of the positions in the new alphabet and check them carefully using frequency arrays.

Source codes

The source codes in C++ and Python can be seen below.

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    string a, b;
    cin >> a;
    cin >> b;

    vector<int> poz(26);
    for(int i = 0; i < 26; i++)
        poz[a[i] - 'a'] = i;

    int cnt = 1;
    for(int i = 1; i < b.size(); i++)
        if(poz[b[i] - 'a'] <= poz[b[i-1] - 'a'])
            cnt++;

    cout << cnt;
    return 0;
}

a = input()
b = input()

poz = {char: i for i, char in enumerate(a)}

cnt = 1
for i in range(1, len(b)):
    if poz[b[i]] <= poz[b[i - 1]]:
        cnt += 1

print(cnt)