首页 > 试题广场 >

小红的双生串

[编程题]小红的双生串

热度指数：3995 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

$\hspace{15pt}$ 小红定义一个字符串是双生串，当且仅当其前半部分所有字符相同，后半部分所有字符相同。
$\hspace{15pt}$ 现在，小红拿到了一个字符串 $s$ ，她每次操作可以修改一个字符。小红希望你求出将其修改为双生串的最小修改次数。

输入描述:

在一行上输入一个长度为  且为偶数，仅由小写字母构成的字符串 ，代表待修改的字符串。

输出描述:

输出一个整数，表示将  修改为双生串的最小修改次数。

示例1

输入

popipa

输出

说明

在这个样例中，将  修改为  是其中一个最优解。

示例2

输入

aaaa

输出

说明

在这个样例中，给定的字符串已经是双生串，不需要修改。

算法知识视频讲解

Python3

牛客341639822号

from collections import Counter
st = input()
mid = len(st)//2 st1 = st[:mid]
st2 = st[mid:]
st1_list = sorted(Counter(st1).items(), key=lambda d: d[1], reverse=True)
st2_list = sorted(Counter(st2).items(), key=lambda d: d[1], reverse=True)
c = len(st)-st1_list[0][1]-st2_list[0][1] print(c)

发表于 2025-10-02 22:26:58 回复(0)

Python3

星辰2025

a = list(input())
def fun(l):
    b = len(l)
    c = list(set(l))
    d = 1
    for i in c:
        if l.count(i) > d:
            d = l.count(i)
    return b - d
if len(list(set(a))) == 1:
    print(0)
else:
    e = len(a) // 2
    print(fun(a[:e])+fun(a[e:]))

这个怎么分类到动态规划，有动态规划的解法吗

发表于 2025-08-28 17:02:44 回复(1)

Python3

天天摸鱼的干饭人很活跃

from collections import Counter

s = str(input())

n = int(len(s) / 2)

s1 = s[:n]

s2 = s[:n-1:-1]

c1 = Counter(s1)

c2 = Counter(s2)

n1 = max(c1.values())

n2 = max(c2.values())

print(2*n -n1 -n2)

发表于 2025-06-30 17:42:31 回复(0)

Python3

theyoungestontop

s = input().strip()
if not (1<=len(s)<=2*10**5 and len(s)%2==0 and all(si.isalpha() and si.islower() for si in s)):
    print('请输入有效长度内且为偶数，仅由小写字母构成的字符串s')
else:
    shalf = len(s)//2
    fores = s[:shalf]
    backs = s[shalf:]
    forec = {}
    backc = {}
    for si in fores:
        forec[si] = forec.get(si, 0) + 1
    num = shalf - max(forec.values())
    for si in backs:
        backc[si] = backc.get(si, 0) + 1
    num += shalf - max(backc.values())
    print(num)

发表于 2025-06-10 16:26:31 回复(0)

Python3

dk斗志昂扬

s = list(input())
max_cnt_l, max_cnt_r, L = 0, 0, len(s)//2
for i in s[:L]:
    max_cnt_l = max(max_cnt_l, s[:L].count(i))
for i in s[L:]:
    max_cnt_r = max(max_cnt_r, s[L:].count(i))
print(2*L-max_cnt_l-max_cnt_r)
# 为什么用这个会超时

发表于 2025-05-28 15:33:36 回复(0)

Python3

_Wiii

s=input().strip()
half=len(s)//2
dic_front={}
for char in s[:half]:
    if char in dic_front:
        dic_front[char]+=1
    else:
        dic_front[char]=1
dic_back={}
for char in s[half:]:
    if char in dic_back:
        dic_back[char]+=1
    else:
        dic_back[char]=1
max_front=0
if dic_front:
    max_front=max(dic_front.values())

max_back=0
if dic_back:
    max_back=max(dic_back.values())
print(2*half-max_front-max_back)

发表于 2025-04-27 11:22:30 回复(0)

Python3

海洋游人

# Read before proceeding to the solution:

# Overall logic:

# Given that the given string s has an even number of letters, we know

# that the final string s' should be formed by combining two substrings

# that consist of the same letter. This implies that we can solve this

# problem by splitting the input string in halves, and then identify the

# letter with most occurrences in the substrings. Taking the difference

# (dif) between the length of the halved-string and the number of

# occurrences of the target letter will give us the answer for the

# substring in question. The final answer will be (dif_1 + dif_2).

# Solution:

s = input()

# Write a function that identifies the letter with the highest

# number of occurrences in a string and returns its number of

# occurences:

def max_occ(s):

counts = {}

for letter in s:

if letter in counts:

counts[letter] += 1

else:

counts[letter] = 1

max_count = max(counts.values())

return max_count

def min_chg(s):

hlf_len = int(len(s)/2)

first_hlf = s[0:hlf_len]

second_hlf = s[hlf_len:]

first_hlf_chg = hlf_len - max_occ(first_hlf)

second_hlf_chg = hlf_len - max_occ(second_hlf)

num_chg = first_hlf_chg + second_hlf_chg

return num_chg

print(min_chg(s))

发表于 2025-04-04 17:29:44 回复(0)

Python3

忧伤的双曲线

def appear(s):

set_s = set(s)

dic = {}

for i in s:

if i not in dic.keys():

dic[i] = 1

else:

dic[i] += 1

sorted_set_s = sorted(set_s,key=lambda x:dic[x],reverse=True)

return len(s)-dic[sorted_set_s[0]]

s = input()

s1 = s[:len(s)//2]

s2 = s[len(s)//2:]

print(appear(s1)+appear(s2))

发表于 2025-03-21 12:02:29 回复(0)

Python3

秦小黄

import sys

s=input()

n=len(s)

l1=s[0:int(n/2)]

l2=s[int(n/2):]

d1=dict()

for i in l1:

if i in d1.keys():

d1[i]+=1

else:

d1[i]=1

MAX1=max(d1.values())

d2=dict()

for i in l2:

if i in d2.keys():

d2[i]+=1

else:

d2[i]=1

MAX2=max(d2.values())

print(int(n-MAX1-MAX2))

发表于 2025-03-12 20:45:30 回复(0)

提交观点

问题信息

动态规划

难度：

10条回答 37收藏 529浏览

小红的双生串

输入描述:

输出描述:

输入

输出

说明

输入

输出

说明

问题信息

热门推荐

相关试题