stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include <bits/stdc++.h>

#define N 1000050

using namespace std;



char a[N],b[N];

int flag,ans,n;

queue<int> q;



int main() {

	scanf("%d%s%s",&n,a+1,b+1);

	for (int _=1;_<=n;_++) if (a[_] != b[_]) flag = 1;

	if (!flag) return puts("0"), 0;

	

	int p = n;

	for (int _=n;_>=1;_--) {

		if (b[_-1] == b[_]) continue;

		p = min(p, _);

		while (p && a[p] != b[_]) p--;

		if (!p) return puts("-1"), 0;

		

		#define sz (int)q.size()

		while (!q.empty())

			if (q.front()-sz >= _) q.pop(); else break;

		q.push(p);

		_!=p ? ans = max(ans,sz) :0;

	}

	printf("%d\n",ans+1);

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.267355726722553x):
#include<cstdio>

#include<cstring>

#include<algorithm>

#define For(i,a,b) for(int i=a;i<=b;++i)

#define Fdn(i,b,a) for(int i=b;i>=a;--i)

#define Printno {puts("-1"); return 0;}

using namespace std;

const int MAXN=1000005;



int n,ans,p[MAXN],ed[MAXN],tot;

char a[MAXN],b[MAXN],ch[MAXN];



bool check(int mid){

	Fdn(i,tot,mid+1){

		if(p[i-mid]-mid<ed[i]) return 0;

	}

	return 1;

}



int main(){

	scanf("%d%s%s",&n,a+1,b+1);

	int j=n+1, pr=n;

	bool bo=1;

	Fdn(i,n,1){

		if(b[i-1]!=b[i]){

			j=min(j-1,i);

			while(j>0&&a[j]!=b[i]) j--;

			//printf("%d :find %d\n",i,j);

			if(!j) Printno;

			p[++tot]=j;

			ed[tot]=pr; pr=i-1;

			ch[tot]=b[i];

		}

		if(a[i]!=b[i]) bo=0;

	}

	if(bo){puts("0"); return 0;}

	//Fdn(i,tot,1) printf("test: %d %d\n",p[i],ed[i]);

	p[0]=n+1;

	int l=0, r=tot, mid;

	while(l<=r){

		mid=(l+r)>>1;

		if(check(mid)) ans=mid, r=mid-1; else l=mid+1;

	}

	printf("%d\n",ans);

	

	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

#define N 1000050

using namespace std;



char a[N],b[N];

int flag,ans,n;

queue<int> q;



int main() {

	scanf("%d%s%s",&n,a+1,b+1);

	for (int _=1;_<=n;_++) if (a[_] != b[_]) flag = 1;

	if (!flag) return puts("0"), 0;

	

	int p = n;

	for (int _=n;_>=1;_--) {

		if (b[_-1] == b[_]) continue;

		p = min(p, _);

		while (p && a[p] != b[_]) p--;

		if (!p) return puts("-1"), 0;

		

		#define sz (int)q.size()

		while (!q.empty())

			if (q.front()-sz >= _) q.pop(); else break;

		q.push(p);

		_!=p ? ans = max(ans,sz) :0;

	}

	printf("%d\n",ans+1);

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.268589796421805x):
#include<cstdio>

#include<cstring>

#include<algorithm>

#define For(i,a,b) for(int i=a;i<=b;++i)

#define Fdn(i,b,a) for(int i=b;i>=a;--i)

#define Printno {puts("-1"); return 0;}

using namespace std;

const int MAXN=1000005;



int n,ans,p[MAXN],ed[MAXN],tot;

char a[MAXN],b[MAXN],ch[MAXN];



int main(){

	scanf("%d%s%s",&n,a+1,b+1);

	int j=n+1, pr=n;

	bool bo=1;

	Fdn(i,n,1){

		if(b[i-1]!=b[i]){

			j=min(j-1,i);

			while(j>0&&a[j]!=b[i]) j--;

			//printf("%d :find %d\n",i,j);

			if(!j) Printno;

			p[++tot]=j;

			ed[tot]=pr; pr=i-1;

			ch[tot]=b[i];

		}

		if(a[i]!=b[i]) bo=0;

	}

	if(bo){puts("0"); return 0;}

	//Fdn(i,tot,1) printf("test: %d %d\n",p[i],ed[i]);

	p[0]=n+1;

	For(i,1,tot){

		while(p[i-ans]-ans<ed[i]) ans++;

	}

	printf("%d\n",ans);

	

	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

#define N 1000050

using namespace std;



char a[N],b[N];

int flag,ans,n;

queue<int> q;



int main() {

	scanf("%d%s%s",&n,a+1,b+1);

	for (int _=1;_<=n;_++) if (a[_] != b[_]) flag = 1;

	if (!flag) return puts("0"), 0;

	

	int p = n;

	for (int _=n;_>=1;_--) {

		if (b[_-1] == b[_]) continue;

		p = min(p, _);

		while (p && a[p] != b[_]) p--;

		if (!p) return puts("-1"), 0;

		

		#define sz (int)q.size()

		while (!q.empty())

			if (q.front()-sz >= _) q.pop(); else break;

		q.push(p);

		_!=p ? ans = max(ans,sz) :0;

	}

	printf("%d\n",ans+1);

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.269134698562653x):
#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

using namespace std;

 

typedef long long ll;

const int MAXN=1e7+5;

 

int n,ans;

int deq[MAXN],l,r;

char s[MAXN],t[MAXN];

 

int main(){

 

    scanf("%d%s%s",&n,s+1,t+1);

    if(strcmp(s+1,t+1)==0) return puts("0"),0;

    l=1,r=0;

    for(int i=n,j=n;i>=1;i--){

        if(t[i]==t[i-1]) continue;

        j=min(i,j);

        while(j&&t[i]!=s[j]) j--;

        if(!j) return puts("-1"),0;

        while(l<=r){

            if(deq[l]-(r-l)>i) l++;

            else break;

        }

        deq[++r]=j;

        if(i!=j) ans=max(ans,r-l+1);

    }

    printf("%d",ans+1);

 

    fclose(stdin);

    fclose(stdout);

}
// Slower C++ solution:
#include <bits/stdc++.h>

#define N 1000050

using namespace std;



char a[N],b[N];

int flag,ans,n;

queue<int> q;



int main() {

	scanf("%d%s%s",&n,a+1,b+1);

	for (int _=1;_<=n;_++) if (a[_] != b[_]) flag = 1;

	if (!flag) return puts("0"), 0;

	

	int p = n;

	for (int _=n;_>=1;_--) {

		if (b[_-1] == b[_]) continue;

		p = min(p, _);

		while (p && a[p] != b[_]) p--;

		if (!p) return puts("-1"), 0;

		

		#define sz (int)q.size()

		while (!q.empty())

			if (q.front()-sz >= _) q.pop(); else break;

		q.push(p);

		_!=p ? ans = max(ans,sz) :0;

	}

	printf("%d\n",ans+1);

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.267189918540408x):
#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=1e6+5;

typedef long long ll;

char S[N],T[N];

int n;

int s,t,q[N];

int main()

{

    scanf("%d",&n);

    scanf("%s",S+1);

    scanf("%s",T+1);

    if(strcmp(S+1,T+1)==0){

        puts("0");

        return 0;

    }

    s=1,t=0;

    int p=n;

    int ans=0;

    for(int i=n;i>=1;i--){

        if(T[i]==T[i-1])

            continue;

        p=min(p,i);

        while(p&&T[i]!=S[p])

            p--;

        if(!p){

            puts("-1");

            return 0;

        }

        while(s<=t&&q[s]-(t-s+1)+1>i)

            s++;

        q[++t]=p;

        if(i!=p)

            ans=max(ans,t-s+1);

    }

    printf("%d\n",ans+1);

}
// Slower C++ solution:
#include <bits/stdc++.h>

#define N 1000050

using namespace std;



char a[N],b[N];

int flag,ans,n;

queue<int> q;



int main() {

	scanf("%d%s%s",&n,a+1,b+1);

	for (int _=1;_<=n;_++) if (a[_] != b[_]) flag = 1;

	if (!flag) return puts("0"), 0;

	

	int p = n;

	for (int _=n;_>=1;_--) {

		if (b[_-1] == b[_]) continue;

		p = min(p, _);

		while (p && a[p] != b[_]) p--;

		if (!p) return puts("-1"), 0;

		

		#define sz (int)q.size()

		while (!q.empty())

			if (q.front()-sz >= _) q.pop(); else break;

		q.push(p);

		_!=p ? ans = max(ans,sz) :0;

	}

	printf("%d\n",ans+1);

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.267799832242574x):
#include<cstdio>

#include<cstring>

#include<cmath>

#include<vector>

#include<queue>

#define SF scanf

#define PF printf

#define MAXN 2000010

using namespace std;

typedef long long ll;

char s[MAXN];

char t[MAXN];

int pre[MAXN];

int n,las,cnt=1,ans,add;

int main(){

	SF("%d",&n);

	SF("%s",s+1);

	SF("%s",t+1);

	int las=n;

	bool flag=0;

	for(int i=1;i<=n;i++)

		if(s[i]!=t[i])

			flag=1;

	if(flag==0){

		PF("0");

		return 0;	

	}

	int now=1;

	for(int i=n;i>=1;i--){

		if(i==1||t[i]!=t[i-1]){

			las=min(las,i);

			while(las>0&&s[las]!=t[i])

				las--;

			if(las==0){

				PF("-1");

				return 0;

			}

			add++;

			pre[las+add]--;

			if(las+add>=i+add)

				now--;

			now++;

			ans=max(ans,now);

			continue;

		}

		now+=pre[i+add];

	}

	PF("%d",ans);

}
// Slower C++ solution:
#include <algorithm>

#include <iostream>

#include <cstdio>

#include <queue>



const int MAXN = 1e6 + 10;



class no_solution: std::exception

{

public:

	const char * what() const noexcept

	{

		return "There is no solution under such constrains";

	}

};



int len;

char a[MAXN], b[MAXN];



auto findSolution() -> std::deque<int>::size_type

{

	std::deque<int>::size_type answer = 0;

	std::deque<int> DQ;

	DQ.push_back(len + 1);



	int k = len + 1, offset = 0;

	for (int i = len; i > 0; i--)

	{

		int t = k;

		k = std::min(i, k);

		while (k && a[k] != b[i])

			k--;

		if (k <= 0)

			throw no_solution();



		if (k == t)

		{

			while (!DQ.empty() && DQ.back() + offset >= i)

				DQ.pop_back();

			DQ.push_back(i - offset);

		}

		else

		{

			offset--;

			if (i != k)

				answer = std::max(answer, DQ.size()), DQ.push_front(k - offset);

		}

	}

	return answer;

}



int main()

{

	std::cin >> len >> (a+1) >> (b+1) ;



	try

	{

		std::cout << findSolution() << std::endl ;

	}

	catch(no_solution & x)

	{

		std::cout << "-1" << std::endl ;

		std::cerr << x.what() << std::endl ;

	}



	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 5.515086775364807x):
#include<cstdio>

#include<cstring>

#include<cmath>

#include<vector>

#include<queue>

#define SF scanf

#define PF printf

#define MAXN 2000010

using namespace std;

typedef long long ll;

char s[MAXN];

char t[MAXN];

int pre[MAXN];

int n,las,cnt=1,ans,add;

int main(){

	SF("%d",&n);

	SF("%s",s+1);

	SF("%s",t+1);

	int las=n;

	bool flag=0;

	for(int i=1;i<=n;i++)

		if(s[i]!=t[i])

			flag=1;

	if(flag==0){

		PF("0");

		return 0;	

	}

	int now=1;

	for(int i=n;i>=1;i--){

		if(i==1||t[i]!=t[i-1]){

			las=min(las,i);

			while(las>0&&s[las]!=t[i])

				las--;

			if(las==0){

				PF("-1");

				return 0;

			}

			add++;

			pre[las+add]--;

			if(las+add>=i+add)

				now--;

			now++;

			ans=max(ans,now);

			continue;

		}

		now+=pre[i+add];

	}

	PF("%d",ans);

}
// Slower C++ solution:
#include<iostream>

#include<cstdio>

#include<queue>

#include<algorithm>

using namespace std;

int n;

char a[1000010],b[1000010];

int main(){

	scanf("%d",&n);

	scanf("%s",a+1);

	scanf("%s",b+1);

	bool flag=1;

	for(int i=1;i<=n;++i)if(a[i]!=b[i])flag=0;

	if(flag){

		cout<<0;

		return 0;

	}

	queue<int> q;

	int pos=n,ans=0;

	for(int i=n;i>=1;--i){

		if(b[i]==b[i-1])continue;

		pos=min(pos,i);

		while(pos&&a[pos]!=b[i])pos--;

		if(!pos){

			cout<<-1;

			return 0;

		}

		while(!q.empty()){

			if(q.front()-q.size()>=i)q.pop();

			else break;

		}

		q.push(pos);

		if(i!=pos)ans=max(ans,(int)q.size());

	}

	cout<<ans+1;

}

// Faster C++ solution for the same problem (measured speedup: 5.3051627191470745x):
#include <cstdio>

#include <algorithm>



const int maxn=1000000;



int n,ans,sum[maxn+10];

char s[maxn+10],t[maxn+10];



int main()

{

  scanf("%d%s%s",&n,s+1,t+1);

  if(s[1]!=t[1])

    {

      puts("-1");

      return 0;

    }

  int f=0,k=0,now=n;

  for(int i=n; i; --i)

    {

      f+=sum[i+k];

      if((now>i)||(t[i]!=s[now]))

        {

          while((now>0)&&((now>i)||(t[i]!=s[now])))

            {

              --now;

            }

          if(now==i)

            {

              continue;

            }

          if(now<=0)

            {

              puts("-1");

              return 0;

            }

          ++k;

          ++f;

          sum[i+k-1]=0;

          --sum[now+k-1];

        }

      ans=std::max(ans,f);

    }

  printf("%d\n",ans);

  return 0;

}
// Slower C++ solution:
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>

#include <sstream>

#include <iomanip>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <cctype>

#include <cstring>

#include <vector>

#include <list>

#include <queue>

#include <deque>

#include <stack>

#include <map>

#include <set>

#include <algorithm>

#include <iterator>

#include <bitset>

#include <ctime>

#include<complex>

using namespace std;



#define FOR(i,a,b) for (int i = (a); i < (b); i++)

#define RFOR(i,b,a) for (int i = (b)-1; i >= (a); i--)

#define ITER(it,a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); it++)

#define FILL(a,value) memset(a, value, sizeof(a))



#define SZ(a) (int)a.size()

#define ALL(a) a.begin(), a.end()

#define PB push_back

#define MP make_pair



typedef long long LL;

typedef vector<int> VI;

typedef pair<int, int> PII;



const double PI = acos(-1.0);

const int INF = 1000 * 1000 * 1000 + 7;

const LL LINF = INF * (LL)INF;



const int MAX = 1000 * 1000 + 47;



int SH[MAX];

int R[MAX];

int L[MAX];

int H[MAX];



string s, t;



void imp()

{

	cout << -1 << endl;

	exit(0);

}



int main()

{

	//freopen("in.txt", "r", stdin);

	//freopen("out.txt", "w", stdout);

	ios::sync_with_stdio(false); cin.tie(0);

	int n;

	cin >> n >> s >> t;

	if (s == t)

	{

		cout << 0 << endl;

		return 0;

	}



	FOR(i, 0, n)

	{

		R[i] = -1;

	}

	int p = n - 1;



	RFOR(i, n, 0)

	{

		while (p != -1 && t[i] != s[p]) p--;

		if (p == -1) imp();

		L[p] = i;

		R[p] = max(i, R[p]);

		if (i == p) p--;

	}



	int sh = 0, add = 0;

	int ans = 0;

	RFOR(i, n, 0)

	{

		H[i + sh] = -add;

		if (R[i] == -1)

		{

			continue;

		}



		ans = max(ans, H[R[i] + sh] + add + 1);

		sh++;

		add++;

	}



	//FOR(i, 0, n)

	//{

	//	cout << R[i] << " ";

	//}

	//cout << endl;

	//FOR(i, 0, n)

	//{

	//	cout << H[i] << " ";

	//}

	//cout << endl;

	cout << ans << endl;

}

// Faster C++ solution for the same problem (measured speedup: 5.364826525642811x):
#include<cstdio>

#include<cstring>

#define MAXN 1000006

#include<algorithm>

using namespace std;

int ans,n,l,cnt,r,q[MAXN];

char s[MAXN],t[MAXN];

int main()

{

	//freopen("blank.in","r",stdin);

	//freopen("blank.out","w",stdout);

	scanf("%d",&n);

	scanf("%s",s+1);

	scanf("%s",t+1);

	l=1;

	if(!strcmp(s+1,t+1))

	{

		printf("0");

		return 0;

	}

	for(int i=n,j=n;i>=1;i--)

	{

		if(t[i]==t[i-1]) continue;

		j=min(i,j);

		while(j&&t[i]!=s[j]) 

			j--;

		if(!j)

		{

			printf("-1");

			return 0;

		}

		while(l<=r)

		{

			if(q[l]-(r-l)>i) l++;

			else break;

		}

		q[++r]=j;

		if(i!=j) ans=max(ans,r-l+1);

	}

	printf("%d\n",++ans);

}
// Slower C++ solution:
//#pragma GCC optimize(3)

#include<iostream>

#include<iomanip>

#include<stack>

#include<queue>

#include<list>

#include<vector>

#include<set>

#include<map>

#include<string>

#include<algorithm>

#include<cmath>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<ctime>

#define ll long long

#define db double

#define mxlen 1000+9

#define inf 1000009

#define INF (int)1e9

#define pi acos(-1)

#define rd(n) {n=0;char ch;int f=0;do{ch=getchar();if(ch=='-'){f=1;}}while(ch<'0'||ch>'9');while('0'<=ch&&ch<='9'){n=(n<<1)+(n<<3)+ch-48;ch=getchar();}if(f)n=-n;}

using namespace std;



char s1[inf],s2[inf];

int q[inf*2],head=inf,tail=inf-1;



int main(){

	int n;

	rd(n)

	scanf("%s%s",&s1,&s2);

	q[++tail]=n+1;

	int pos=n+1,cnt=0,ans=0;

	for (int i=n;i>=1;i--){

		int tmp=pos;

		while (pos>0 && (pos>i || s1[pos-1]!=s2[i-1])){

			pos--;

		}

		if (pos==0){

			puts("-1");

			return 0;

		}

		if (tmp==pos){

			while (head<=tail && q[tail]-cnt>=i){

				tail--;

			}

			q[++tail]=i+cnt;

		}

		else{

			cnt++;

			if (i!=pos){

				ans=max(ans,tail-head+1);

				q[--head]=pos+cnt;

			}

		}

	}

	printf("%d\n",ans);

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.226637644267331x):
#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=1145141;

int n;

char s0[N],s1[N];

int pre[N],lst[133];

int g[N];

int ans,tmp;

int main()

{

	scanf("%d%s%s",&n,s0+1,s1+1);

	int k=0,nw=n;

	for(int i=n;i;i--)

	{

		tmp+=g[i+k];

		if(nw>i||(s0[nw]!=s1[i]))

		{

			while(nw>0&&(nw>i||(s0[nw]!=s1[i]))) nw--;

			if(nw==i) continue;

			if(nw<=0){puts("-1");return 0;}

			k++,tmp++;

			g[i+k-1]=0,g[nw+k-1]--;

		}

		ans=max(ans,tmp);

	}

	printf("%d\n",ans);

    return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

#define MAXN 1000005

using namespace std;



int n,pos,ans,head,tail;

int q[MAXN];

char s[MAXN],t[MAXN];



int min(int a,int b) {return a<b?a:b;}

int max(int a,int b) {return a>b?a:b;}



template<class T>inline void read(T &res)

{

    static char ch;T flag=1;

    while((ch=getchar())<'0'||ch>'9')if(ch=='-')flag=-1;res=ch-48;

    while((ch=getchar())>='0'&&ch<='9')res=res*10+ch-48;res*=flag;

}



int main()

{

    read(n);

    scanf("%s%s",s+1,t+1);

    if(strcmp(s+1,t+1)==0){putchar('0');return 0;}

    pos=n;head=1;tail=0;

    for(int i=n;i>=1;i--)

    {

        if(t[i]==t[i-1]) continue;

        pos=min(pos,i);

        while(pos&&t[i]!=s[pos]) pos--;

        if(pos==0) {putchar('-');putchar('1');return 0;}

        while(head<=tail)

        {

            if(q[head]-(tail-head+1)+1>i) head++;

            else break;

        }

        q[++tail]=pos;

        if(i!=pos) ans=max(ans,tail-head+1);

    }

    printf("%d\n",ans+1);

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.224739138743966x):
#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=1145141;

int n;

char s0[N],s1[N];

int pre[N],lst[133];

int g[N];

int ans,tmp;

int main()

{

	scanf("%d%s%s",&n,s0+1,s1+1);

	int k=0,nw=n;

	for(int i=n;i;i--)

	{

		tmp+=g[i+k];

		if(nw>i||(s0[nw]!=s1[i]))

		{

			while(nw>0&&(nw>i||(s0[nw]!=s1[i]))) nw--;

			if(nw==i) continue;

			if(nw<=0){puts("-1");return 0;}

			k++,tmp++;

			g[i+k-1]=0,g[nw+k-1]--;

		}

		ans=max(ans,tmp);

	}

	printf("%d\n",ans);

    return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define REP(i,a,b) for(int i=(a),_end_=(b);i<=_end_;i++)

#define DREP(i,a,b) for(int i=(a),_end_=(b);i>=_end_;i--)

#define EREP(i,u) for(int i=start[u];i;i=e[i].next)

#define fi first

#define se second

#define mkr(a,b) make_pair(a,b)

#define SZ(A) ((int)A.size())

template<class T>inline void chkmin(T &a,T b){ if(a>b)a=b;}

template<class T>inline void chkmax(T &a,T b){ if(a<b)a=b;}

inline int read()

{

	int s=0,f=1; char ch=getchar();

	while(!isdigit(ch) && ch!='-')ch=getchar();

	if(ch=='-')ch=getchar(),f=-1;

	while(isdigit(ch))s=s*10+ch-'0',ch=getchar();

	return ~f?s:-s;

}



const int maxn=1e6+20;



int n;

char S[maxn],T[maxn];



inline void init()

{

	n=read();

	scanf("%s",S+1);

	scanf("%s",T+1);

}



int ans;



inline void doing()

{

	deque<int>q;q.push_back(n+1);

	for(int i=n,j=n+1,del=0;i;i--)

	{

		int tmp=j;

		while(j && (j>i || S[j]!=T[i]))j--;

		if(!j)puts("-1"),exit(0);

		if(j==tmp)

		{

			while(!q.empty() && q.back()-del>=i)q.pop_back();

			q.push_back(i+del); 

		}else

		{

			del++;

			if(i!=j)

			{

				chkmax(ans,SZ(q));

				q.push_front(j+del);

			}

		}

	}

	printf("%d\n",ans);

}



int main()

{

	init();

	doing();

	return 0;

}




// Faster C++ solution for the same problem (measured speedup: 5.264547173908033x):
#include<cstdio>

#include<algorithm>

const int N=1000007;

char s[N],t[N];int n,ans,sum[N];

int main()

{

    scanf("%d%s%s",&n,s+1,t+1);

    if(s[1]^t[1]) return !printf("-1");

    for(int i=n,f=0,k=0,p=n;i;--i)

    {

	f+=sum[i+k];

	if(p>i||t[i]^s[p])

        {

	    for(;p>0&&(p>i||t[i]^s[p]);--p);

	    if(p==i) continue;

	    if(p<=0) return !printf("-1");

	    ++k,++f,sum[i+k-1]=0,--sum[p+k-1];

        }

	ans=std::max(ans,f);

    }

    printf("%d",ans);

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define REP(i,a,b) for(int i=(a),_end_=(b);i<=_end_;i++)

#define DREP(i,a,b) for(int i=(a),_end_=(b);i>=_end_;i--)

#define EREP(i,u) for(int i=start[u];i;i=e[i].next)

#define fi first

#define se second

#define mkr(a,b) make_pair(a,b)

#define SZ(A) ((int)A.size())

template<class T>inline void chkmin(T &a,T b){ if(a>b)a=b;}

template<class T>inline void chkmax(T &a,T b){ if(a<b)a=b;}

inline int read()

{

	int s=0,f=1; char ch=getchar();

	while(!isdigit(ch) && ch!='-')ch=getchar();

	if(ch=='-')ch=getchar(),f=-1;

	while(isdigit(ch))s=s*10+ch-'0',ch=getchar();

	return ~f?s:-s;

}



const int maxn=1e6+20;



int n;

char S[maxn],T[maxn];



inline void init()

{

	n=read();

	scanf("%s",S+1);

	scanf("%s",T+1);

}



int ans;



inline void doing()

{

	deque<int>q;q.push_back(n+1);

	for(int i=n,j=n+1,del=0;i;i--)

	{

		int tmp=j;

		while(j && (j>i || S[j]!=T[i]))j--;

		if(!j)puts("-1"),exit(0);

		if(j==tmp)

		{

			while(!q.empty() && q.back()-del>=i)q.pop_back();

			q.push_back(i+del); 

		}else

		{

			del++;

			if(i!=j)

			{

				chkmax(ans,SZ(q));

				q.push_front(j+del);

			}

		}

	}

	printf("%d\n",ans);

}



int main()

{

	init();

	doing();

	return 0;

}




// Faster C++ solution for the same problem (measured speedup: 5.2643218371917095x):
#include <cstdio>

#include <vector>

#include <algorithm>

#include <set>

#include <cstring>

#include <map>

using namespace std;

const int MAXN = 1000005;

char S[MAXN], T[MAXN];

int n, q[MAXN], head = 1, tail;

signed main () {

	scanf("%d%s%s", &n, S+1, T+1);

	if(strcmp(S+1, T+1) == 0) { puts("0"); return 0; }

	int ans = 0;

	for(int i = n, j = n; i >= 1; --i) {

		if(T[i] == T[i-1]) continue;

		j = min(j, i);

		for(; j && S[j] != T[i]; --j);

		if(!j) { puts("-1"); return 0; }

		while(head <= tail && q[head] - (tail-head+1) + 1 > i) ++head;

		q[++tail] = j;

		if(i != j) ans = max(ans, tail-head+1);

	}

	printf("%d\n", ans+1);

}
// Slower C++ solution:
#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

#define N 1000005

queue<int> q;

char a[N],b[N];

int main()

{

	int n,i,j,ans=0;

	scanf("%d%s%s",&n,a+1,b+1);

	if(strcmp(a+1,b+1)==0){printf("0");return 0;}

	i=j=n;

	while(j){

		while(j&&b[j]==b[j-1])j--;

		while(i&&(i>j||a[i]!=b[j]))i--;

		if(i==0){printf("-1");return 0;}

		while(!q.empty()&&q.front()-(int)q.size()>=j)q.pop();

		if(i!=j)q.push(i);

		ans=max(ans,(int)q.size()+1);

		j--;

	}

	printf("%d",ans);

}

// Faster C++ solution for the same problem (measured speedup: 4.937042257246115x):
#include <cstdio>

#include <vector>

#include <algorithm>

#include <set>

#include <cstring>

#include <map>

using namespace std;

const int MAXN = 1000005;

char S[MAXN], T[MAXN];

int n, q[MAXN], head = 1, tail;

signed main () {

	scanf("%d%s%s", &n, S+1, T+1);

	if(strcmp(S+1, T+1) == 0) { puts("0"); return 0; }

	int ans = 0;

	for(int i = n, j = n; i >= 1; --i) {

		if(T[i] == T[i-1]) continue;

		j = min(j, i);

		for(; j && S[j] != T[i]; --j);

		if(!j) { puts("-1"); return 0; }

		while(head <= tail && q[head] - (tail-head+1) + 1 > i) ++head;

		q[++tail] = j;

		if(i != j) ans = max(ans, tail-head+1);

	}

	printf("%d\n", ans+1);

}