#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int N=2e5+10;
int mp[N];
bool check(int minn,int k,string s,int n){
	int cnt=0;
	for(int len=1;len<=minn;len++){
		memset(mp,0,sizeof mp);
		int ans=0;
		for(int i=len;i<=n;i+=minn){
			mp[s[i]-'a']++;
			ans=max(ans,mp[s[i]-'a']);
		}
		cnt+=(n/minn-ans);
		if(cnt>k) return false;
	}
	return true;
}
int main(){
	cin.tie(0),cout.tie(0);
	ios::sync_with_stdio(false);
	int k;
	cin>>k;
	string s;
	cin>>s;
	int n=s.size();
	s=" "+s;
	for(int i=1;i<=n/2;i++){
		if(n%i!=0||!check(i,k,s,n)) continue;
		cout<<i;
		return 0;
	}
	cout<<n;
	return 0;
}