Delete subsequence ＜ daily question ＞

subject ：

---

Topic link ： Sign in — major IT Written interview preparation platform _ Cattle from

---

The question is s Can delete t The maximum number of times

It's actually greedy Thought

Ideas 1： about s Take the largest in the string t character string

We can use an array to record t In a string

The order in which each character appears

Re traversal s Array

about s Each in the array t Some characters in

Count the number of occurrences

But pay attention to the design constraints

When traversing s Every time s The characters of

The number of occurrences should be less than that in

t The number of characters before the position in

In this way, we can count all the results that meet the conditions

（ reason ： It is equivalent to following t The order of strings is counted ）

Ideas 2： Suppose we were s The string can be deleted at most n Substring

So how can we delete to achieve deletion n Secondary string Le

The answer is from No n The secondary string starts to be deleted

And No n All characters after the secondary character can be deleted ( It has no effect on the number of times )

Then delete n-1 Second string

Then delete it one by one

In this way, you can ensure that you can delete n All strings at once

（ reason ： Every deletion from the back to the front ensures

It will not affect the strings that meet the conditions above

Deleting in turn can ensure the maximum number of deletes ）

---

Ideas 1 Code details ：

#include<stdio.h>
#include<iostream>
using namespace std;
typedef long long ll;
#include<string.h>
using namespace std;
int n, m;
int pos[30], ans[30];
string s, t;
int main()
{
	int ts;
	cin >> ts;
	while (ts--)
	{
		scanf("%d%d", &n, &m);
		memset(pos, -1, sizeof(pos));
		memset(ans, 0, sizeof(ans));// Each sample needs to initialize the array 
		cin >> s >> t;
		for (int i = 0; i < m; i++) pos[t[i] - 'a'] = i;// Record t The order in which each character appears in the array 

		for (int i = 0; i < n; i++)
		{
			if (s[i] == t[0]) ans[0]++;// about t Count the number of the first character of 
			else
			{
				int step = pos[s[i] - 'a'];
				if (step!= -1 && ans[step] < ans[step - 1])
					ans[step]++;// Code key ！ If s The character in exists in t in , And the number of occurrences is less than that of the character in t The previous character in . Then the number can be increased 1
			}
		}
		printf("%d\n", ans[m - 1]);// The output finally meets t Number of strings of sequence conditions 
	}
	return 0;
}

---

Ideas 2 Code （ Official code ）：

#include <bits/stdc++.h>
typedef unsigned long long ull;
typedef long long ll;
#define inf 0x3f3f3f3f
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define nep(i, r, l) for (int i = r; i >= l; i--)
void sc(int &x) { scanf("%d", &x); }
void sc(int &x, int &y) { scanf("%d%d", &x, &y); }
void sc(int &x, int &y, int &z) { scanf("%d%d%d", &x, &y, &z); }
void sc(ll &x) { scanf("%lld", &x); }
void sc(ll &x, ll &y) { scanf("%lld%lld", &x, &y); }
void sc(ll &x, ll &y, ll &z) { scanf("%lld%lld%lld", &x, &y, &z); }
void sc(char *x) { scanf("%s", x); }
void sc(char *x, char *y) { scanf("%s%s", x, y); }
void sc(char *x, char *y, char *z) { scanf("%s%s%s", x, y, z); }
void out(int x) { printf("%d\n", x); }
void out(ll x) { printf("%lld\n", x); }
void out(int x, int y) { printf("%d %d\n", x, y); }
void out(ll x, ll y) { printf("%lld %lld\n", x, y); }
void out(int x, int y, int z) { printf("%d %d %d\n", x, y, z); }
void out(ll x, ll y, ll z) { printf("%lld %lld %lld\n", x, y, z); }
void ast(ll x,ll l,ll r){assert(x>=l&&x<=r);}
using namespace std;
const int N=1e6+5,mod=998244353;
int n,m;
char s[N],t[N];
int main()
{
  // freopen("1.in", "r",stdin);
  //   freopen("1.out", "w", stdout);
  int ts;sc(ts);ast(ts,1,10000);
  int sum=0;
  while(ts--)
  {
    scanf("%d%d",&n,&m);
    sc(s+1);sc(t+1);
    ast(n,1,1000000);ast(m,1,min(n,26));
    sum+=n;
    ast(sum,1,1000000);
    assert(strlen(s+1)==n);assert(strlen(t+1)==m);
    rep(i,1,n) ast(s[i],'a','z');
    rep(i,1,m) ast(t[i],'a','z');
    for(int i=1;i<=m;i++)
      for(int j=i+1;j<=m;j++) assert(t[i]!=t[j]);
    vector<int>vc[26];
    rep(i,1,n)
      vc[s[i]-'a'].emplace_back(i);
    int ans=0;
    while(true)
    {
      bool flag=true;
      int las=n+1;
      for(int i=m;i>=1;i--)
      {
        while(vc[t[i]-'a'].size()&&vc[t[i]-'a'].back()>=las) vc[t[i]-'a'].pop_back();
        if(vc[t[i]-'a'].empty()){flag=false;break;}
        las=vc[t[i]-'a'].back();
        vc[t[i]-'a'].pop_back();
      }
      if(!flag) break;
      ans++;
    }
    out(ans);
  }
}

 

PS: The life and death of Gouli country depend on , Is it because of misfortune or good fortune ！____ Lin Zexu 《 Go to the garrison entrance to occupy the family · second 》