They Are Everywhere

时间：2023-03-09 15:23:34
They Are Everywhere
They Are Everywhere

Sergei B., the young coach of Pokemons, has found the big house which consists of n flats ordered in a row from left to right. It is possible to enter each flat from the street. It is possible to go out from each flat. Also, each flat is connected with the flat to the left and the flat to the right. Flat number 1 is only connected with the flat number 2 and the flat number n is only connected with the flat numbern - 1.

There is exactly one Pokemon of some type in each of these flats. Sergei B. asked residents of the house to let him enter their flats in order to catch Pokemons. After consulting the residents of the house decided to let Sergei B. enter one flat from the street, visit several flats and then go out from some flat. But they won't let him visit the same flat more than once.

Sergei B. was very pleased, and now he wants to visit as few flats as possible in order to collect Pokemons of all types that appear in this house. Your task is to help him and determine this minimum number of flats he has to visit.

Input

The first line contains the integer n (1 ≤ n ≤ 100 000) — the number of flats in the house.

The second line contains the row s with the length n, it consists of uppercase and lowercase letters of English alphabet, the i-th letter equals the type of Pokemon, which is in the flat number i.

Output

Print the minimum number of flats which Sergei B. should visit in order to catch Pokemons of all types which there are in the house.

Examples
input
3
AaA
output
2
input
7
bcAAcbc
output
3
input
6
aaBCCe
output
5
Note

In the first test Sergei B. can begin, for example, from the flat number 1 and end in the flat number 2.

In the second test Sergei B. can begin, for example, from the flat number 4 and end in the flat number 6.

In the third test Sergei B. must begin from the flat number 2 and end in the flat number 6.

分析：尺取法；

代码：

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <algorithm>

#include <climits>

#include <cstring>

#include <string>

#include <set>

#include <map>

#include <queue>

#include <stack>

#include <vector>

#include <list>

#include <ext/rope>

#define rep(i,m,n) for(i=m;i<=n;i++)

#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)

#define vi vector<int>

#define pii pair<int,int>

#define mod 1000000007

#define inf 0x3f3f3f3f

#define pb push_back

#define mp make_pair

#define fi first

#define se second

#define ll long long

#define pi acos(-1.0)

const int maxn=1e5+;

const int dis[][]={{,},{-,},{,-},{,}};

using namespace std;

using namespace __gnu_cxx;

ll gcd(ll p,ll q){return q==?p:gcd(q,p%q);}

ll qpow(ll p,ll q){ll f=;while(q){if(q&)f=f*p;p=p*p;q>>=;}return f;}

int n,m,mi,co[],cnt[],all;

char a[maxn];

int main()

{

    int i,j,k,t;

    mi=inf;

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

    rep(i,,n-)if(++co[a[i]]==)all++;

    int l=-,r=,now=;

    for(i=;;i++)

    {

        if(++cnt[a[i]]==)now++;

        if(now==all)break;

    }

    r=i;

    mi=r+;

    while(l<=r&&r<n)

    {

        do{l++;if(--cnt[a[l]]>)mi=min(mi,r-l);else break;}while();

        do{r++;}while(r<n&&++cnt[a[r]]!=);

        if(r<n&&r>=l)mi=min(mi,r-l);

    }

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

    //system ("pause");

    return ;

}

随机推荐

  1. hadoop文件系统浅析

    1.什么是分布式文件系统? 管理网络中跨多台计算机存储的文件系统称为分布式文件系统. 2.为什么需要分布式文件系统了? 原因很简单,当数据集的大小超过一*立物理计算机的存储能力时候,就有必要对它进行 ...

  2. Chapter 2 Open Book——11

    "Hey, Dad, welcome home." hey爸爸,欢迎回家. "Thanks." He hung up his gun belt and step ...

  3. classpath获取--getResource()

    在java中的API里,有两种方式来使用classpath读取资源. 1. Class的getResource() 2. ClassLoader的getResource() 但是两者有一定区别,运行以 ...

  4. Python之路：爬虫之urllib库的基本使用和高级使用

    关于爬虫自己一直在看,所以时间太慢,这才第二更,有等不及的小伙伴可以慢慢的品尝了,在看下面的之前,建议先把上一章看一下.以下是关于python的Urllib的基础和高级用法. 1.如何扒下一个网站,用 ...

  5. Qt Quick 简单教程

    上一篇<Qt Quick 之 Hello World 图文详解>我们已经分别在电脑和 Android 手机上运行了第一个 Qt Quick 示例—— HelloQtQuickApp ,这篇 ...

  6. 安装apache服务出错，无法启动此程序，因为计算机中丢失VCRUNTIME140.dll 尝试重新安装此程序以解决此问题

    错误信息:无法启动此程序,因为计算机中丢失VCRUNTIME140.dll 尝试重新安装此程序以解决此问题 错误场景:在使用["D:\Program Files\httpd-2.4.20-x ...

  7. load

    http://blog.scoutapp.com/articles/2009/07/31/understanding-load-averages http://blog.scoutapp.com/ar ...

  8. Js根据class名替换html标签内容 ，在某标签前后添加内容

    function getClass(obj, attr) { var aArray = [];//定义一个新的空数组 var i = 0; var aAll = document.getElement ...

  9. asp之Eval()函数

    运行字符串: a=Eval("1+1") 结果为:a=2 运行函数: function aa(a) aa=a+1 end function b=Eval("aa(2)&q ...

  10. redis采用序列化方案存对象

    前几天被问到这样一个问题,redis怎么存对象,平时也没怎么注意,只知道redis存字符之类的,不过就是根据键存取值,不过对象的话还是不同的 首先来了解一下为什么要实现序列化 为什么要实现序列化接口 ...

相关文章