Amazon Alexa SDE Hiring Challenge

Good String

Good String

You are given a string S of length N, Q ranges of the form [L, R] in a @D array range, and a permutation arr containing numbers from 1 to N.

Task

In one operation, you remove the first unremoved character as per the permutation. However, the positions of other characters will not change. Determine the minimum number of operations for the remaining string to be good.

Notes

• A string is considered good if all the Q ranges have all distinct characters. Removed characters are note counted.
• A range with all characters removed is considered to have all distinct characters.
• The sequence of n integers is called a permutation if it contains all integers from 1 to n exactly once.
• 1-based indexing is followed.

Solution

• Time : O(logn * (n + qlogn))
• Space : O(n)

#include <bits/stdc++.h>

#pragma optimization_level 3
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#pragma GCC optimize("Ofast")//Comment optimisations for interactive problems (use endl)
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")

struct PairHash {inline std::size_t operator()(const std::pair<int,int> & v) const {return v.first*31+v.second;}};

#define MAX_N 101010
#define INF 987654321
#define EPS 1e-9
#define ll long long
#define pll pair<ll, ll>
#define vpll vector<pll>
#define vall3 vector<array<ll,3>>
#define all3 array<ll,3>
#define all5 array<ll,5>
#define vall5 vector<all5>
#define vll vector<ll>
#define vi vector<int>
#define vs vector<string>
#define usll unordered_set<ll>
#define uspll unordered_set<pll, PairHash>
#define umll unordered_map<ll,ll>
#define vvs vector<vs>
#define vvll vector<vll>
#define all(a) begin(a), end(a)
#define rall(a) rbegin(a), rend(a)

ll __gcd(ll x, ll y) { return !y ? x : __gcd(y, x % y); }

using namespace std;
vll A;
vpll Q;
string s;
ll fenwick[26][MAX_N];

void update(ll k, ll n, ll v) {
    while(n < MAX_N) {
        fenwick[k][n] += v;
        n += n & -n;
    }
}

ll query(ll k, ll n) {
    ll res = 0;
    while(n) {
        res += fenwick[k][n];
        n -= n & -n;
    }
    return res;
}

void bulkUpdate(ll f, ll e, ll v) {
    for(ll i = f; i <= e; i++) {
        ll idx = A[i];
        ll k = s[idx - 1] - 'a';
        update(k, idx, v);
    }
}

bool helper(ll k, ll prv) {
    if(prv < k) bulkUpdate(prv + 1, k, -1);
    else bulkUpdate(k + 1, prv, 1);

    for(auto& [l, r] : Q) {
        for(ll i = 0; i < 26; i++) {
            if(query(i, r) - query(i, l - 1) > 1)
                return false;
        }
    }
    return true;
}

ll solve() {
    ll n = s.length(), l = 0, r = n, res = LLONG_MAX, prv = 0;
    memset(fenwick, 0, sizeof fenwick);
    for(ll i = 0; i < n; i++) {
        ll k = s[i] - 'a';
        update(k, i + 1, 1);
    }
    while(l <= r) {
        ll m = l + (r - l) / 2;
        bool p = helper(m, prv);
        if(p) res = min(res, m);
        if(p) r = m - 1;
        else l = m + 1;
        prv = m;
    }


    return res;
}

int main() {
    ios_base::sync_with_stdio(0);
    ios::sync_with_stdio(0);
    cin.tie(0);
    ll tc = 1;
    cin>>tc;
    for(ll i = 1; i <= tc; i++) {
        ll n, q;
        cin>>n>>q;
        cin>>s;
        A = vll(n + 1);
        Q = vpll(q);
        for(ll j = 1; j <= n; j++) cin>>A[j];
        for(ll j = 0; j < q; j++) cin>>Q[j].first>>Q[j].second;
        cout<<solve()<<endl;
    }
    return 0;
}