美团2021春招实习笔试题——计算关键串字串的串数

标题美团2021春招实习笔试题——计算关键串字串的串数

时间限制： 3000MS 内存限制： 589824KB 题目描述： 定义一个字符串为关键串当且仅当该串中出现次数最多的字符严格超过了字符总数（即串长）的一半。

例如字符串"a",“aab”,“aaab”,“abccc"是关键串，而"ab”,“abc”,“aabb”,"abcc"不是。

给一个长度为n的字符串s，有多少个子串是关键串？

子串：对于一个给定的字符串，串中任意个连续的字符组成的子序列称为该串的子串。

输入描述
第一行是一个正整数n，表示字符串的长度。

第二行是一个长度为n的仅包含小写字母的字符串s。

输出描述
输出一行，表示字符串s中是关键串的子串个数。

n=int(input())
s_lis=list(input())

count=0
def is_key_string(s):
    count_lis=[]
    for item in s:
        count_lis.append(s.count(item))
    if max(count_lis)>len(s)/2:
        return True
    else:
        return False
child_string_lis=[s_lis[i:i + x + 1] for x in range(len(s_lis)) for i in range(len(s_lis) - x)]
#print(child_string_lis)
child_string_lis=list(set(tuple(t)for t in child_string_lis))
for item in child_string_lis:
    if is_key_string(item):
        count+=1
print(count)