MENU

Polycarp and Letters 题解 | ACM

March 20, 2019 • 我爱学习

题目大意已知一个只包含大写字母和小写字母的字符串 s.
现在有这样一个集合:它可以包含字符串中不同小写字母的位置,但是这些位置中任意两个之间不能有大写字母.
现在请你写一个程序求集合最大时的大小.
输入:第一行一个整数 n (1<=n<=200), 表示字符串的长度 第二行一个字符串 s
输出:这个集合最大时的大小
输入数据 The first line contains a single integer n n ( 1<=n<=200 1<=n<=200 ) — length of string s s .
The second line contains a string s s consisting of lowercase and uppercase Latin letters.
数据输出 Print maximum number of elements in pretty set of positions for string s s .
样例 11
aaaaBaabAbA

12
zACaAbbaazzC

3
ABC
样例输出 2
3
0

思路简述

  • 一个数组,0~25 分别代表 26 个英文字母;
  • 先遍历字符串,从大写字母开始计数
  • 当大写字母之后出现小写字母,开始按照出现的字母进行计数,当计数的时候对应的数组元素值为 0,记录这是一个新的字母。
  • 如果被大写字母中断,则初始化数组。

因此 AC 代码为:

  • #include<stdio.h>
  • #include<string.h>
  • int main()
  • {
  • int ch[30];
  • char s[205];
  • int length;
  • int max,count;
  • while(~scanf("%d",&length))
  • {
  • scanf("%s",s);
  • max = 0;
  • for(int i = 0;i < length;i++)
  • {
  • if(s[i] >= 'a' && s[i] <= 'z')
  • {
  • count = 0;
  • memset(ch,0,sizeof(ch));
  • for(int j = i;s[j] >= 'a' && s[j] <= 'z';j++)
  • {
  • if(ch[s[j]-'a'] == 0)
  • {
  • count++;
  • ch[s[j]-'a']++;
  • }
  • }
  • if(count > max)
  • {
  • max = count;
  • }
  • }
  • }
  • printf("%d\n",max);
  • }
  • return 0;
  • }
Last Modified: September 8, 2021