P3519 [POI2011]ROZ-Difference

    • 61通过
    • 174提交
  • 题目提供者 洛谷
  • 评测方式 云端评测
  • 标签 枚举,暴力 POI 2011 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    A word consisting of lower-case letters of the English alphabet ('a'-'z') is given.

    We would like to choose a non-empty contiguous (i.e. one-piece) fragment of the word so as to maximise the difference in the number of occurrences of the most and the least frequent letter in the fragment.

    We are assuming that the least frequent letter has to occur at least once in the resulting fragment.

    In particular, should the fragment contain occurrences of only one letter, then the most and the least frequent letter in it coincide.

    给一个字符串,求其中的一段,使得出现次数最多的字符与出现次数最少的字符的出现次数之差最大

    输入输出格式

    输入格式:

    The first line of the standard input holds one integer () that denotes the length of the word.

    The second line holds a word consisting of lower-case letters of the English alphabet.

    In tests worth at least 30% of the points it additionally holds that .

    输出格式:

    The first and only line of the standard output is to hold a single integer, equal to the maximum difference in the number of occurrences of the most and the least frequent letter that is attained in some non-empty contiguous fragment of the input word.

    输入输出样例

    输入样例#1: 复制
    10
    aabbaaabab
    输出样例#1: 复制
    3

    说明

    给一个字符串,求其中的一段,使得出现次数最多的字符与出现次数最少的字符的出现次数之差最大 $1 \leq N \leq 10^6$

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。