Good Strings DSA Problem Solution

Good Strings DSA Problem Solution

by

In this post, we are going to solve Good Strings DSA Problem from Amazon’s 10th October Online assessment. Let’s have a look at the problem statement first and then try to solve the problem.

Good Strings DSA Problem Statement

You are given a string

s of length

n,

q ranges of the form

l,r , and an array

arr, containing permutation of numbers from 1 to

n.

In one operation, you remove the first unremoved character as per the permutation. However the positions of the other characters will not change.

A string is considered good, if all the

q ranges have no repeated characters, after ignoring the removed ones. Please note that a range with all characters removed is also considered to be good.

Determine the minimum number of operations required to make the string good.

Input

The first line contains two space separated integers

n and

q.

(1≤n,q≤105)

The second line contains the string

s.

The third line contains

n space separated integers denoting the permutation

arr.

The next

q lines contain 2 integers

l and

r.

(1≤l≤r≤n)

Output

Print an integer denoting the minimum number of operations required to make the string good.

Examples
Input
5 2
aaaaa
2 4 1 3 5
1 2
4 5
Output
2
Input
8 3
abbabaab
6 3 5 1 4 2 7 8
1 3
4 7
3 5
Output
5
Note

For the first sample case, after 2 operations, the string will become “a.a.a” (‘.’ denote removed characters).

So the ranges

(1,2), and

(4,5) both contain single occurrence of ‘a’ Hence, the answer is 2.

Good Strings DSA Problem Solution in C++

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

string transform(vector<int> &v, string &str, int n)
{
string ans = str;
for(int i=0;i<n;i++)
{
ans[v[i]-1] = '.';
}
return ans;
}

bool isvalid(string &str, vector<pair<int,int>> &Q)
{
int n = str.size();
vector<vector<int>> pre(n+1, vector<int>(26, 0));
for(int i=1;i<=n;i++)
{
for(int j=0;j<26;j++)
{
pre[i][j] = pre[i-1][j];
}

if(str[i-1] != '.')
{
pre[i][str[i-1]-'a']++;
}
}

for(auto it: Q)
{
int l = it.first-1, r = it.second;
for(int i=0;i<26;i++)
{
if(pre[r][i] - pre[l][i] > 1)
{
return false;
}
}
}
return true;
}

int main() {
int n,q;
cin>>n>>q;
string str;
cin>>str;
vector<int> v(n);
for(auto &it: v)
{
cin>>it;
}

vector<pair<int,int>> Q(q);
for(int i=0;i<q;i++)
{
cin>>Q[i].first>>Q[i].second;
}

int ans = n + 1;
int lo = 0, hg = n;
while(lo <= hg)
{
int mid = (lo + hg)/2;
string temp = transform(v,str,mid);
if(isvalid(temp, Q))
{
ans = min(ans, mid);
hg = mid-1;
}
else
{
lo = mid+1;
}
}
cout<<ans<<endl;
return 0;
}

Leave a Comment