Problem C: 完美字符串P3
Memory Limit:128 MB
Time Limit:1.000 S
Judge Style:Text Compare
Creator:
Submit:6
Solved:3
Description
你可能见过下面这一句英文:
“The quick brown fox jumps over the lazy dog.”
短短的一句话就包含了所有26个英文字母!因此这句话广泛地⽤于字体效果的展示。更短的还有:
“The five boxing wizards jump quickly.”
所以你很好奇:还有没有更多这样包含所有26个英文字母的句子?于是你⽤爬虫在互联网上爬取了许多英文文本,并且提取出了其中的单词。你现在希望从一个很长的单词序列中找出一段连续出现的单词,它满足:
所有26个英文字母都至少出现一次;
长度尽可能短,即包含的字母总数尽可能少。
“The quick brown fox jumps over the lazy dog.”
短短的一句话就包含了所有26个英文字母!因此这句话广泛地⽤于字体效果的展示。更短的还有:
“The five boxing wizards jump quickly.”
所以你很好奇:还有没有更多这样包含所有26个英文字母的句子?于是你⽤爬虫在互联网上爬取了许多英文文本,并且提取出了其中的单词。你现在希望从一个很长的单词序列中找出一段连续出现的单词,它满足:
所有26个英文字母都至少出现一次;
长度尽可能短,即包含的字母总数尽可能少。
Input
输入的第一⾏包含一个整数n,代表单词序列的长度,即单词的数量。
输入的第⼆⾏包含n个空格分隔的英文单词 (单词仅由⼩写字母构成)。输入数据保证每个⼩写英文字母都至少出现一次。
输入的第⼆⾏包含n个空格分隔的英文单词 (单词仅由⼩写字母构成)。输入数据保证每个⼩写英文字母都至少出现一次。
Output
输出一行一个整数,是你找到的单词序列中的字母总数。
HINT
样例输入
13
there is a quick brown fox jumping over the lazy dog and cat
样例输出
37
最短满⾜条件的单词序列是 “is a quick brown fox jumping over the lazy dog”,共有 37 个字母。
数据规模
对于40%的数据,满⾜n≤100;
对于100%的数据,满⾜1≤n≤100,000。每个单词的长度不超过10个字符,且单词全部由小写英文字母a-z构成。
13
there is a quick brown fox jumping over the lazy dog and cat
样例输出
37
最短满⾜条件的单词序列是 “is a quick brown fox jumping over the lazy dog”,共有 37 个字母。
数据规模
对于40%的数据,满⾜n≤100;
对于100%的数据,满⾜1≤n≤100,000。每个单词的长度不超过10个字符,且单词全部由小写英文字母a-z构成。