首页 > 试题广场 >

小红的双生串

[编程题]小红的双生串

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

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

输入描述:

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

输出描述:

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

示例1

输入

popipa

输出

说明

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

示例2

输入

aaaa

输出

说明

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

算法知识视频讲解

Java

牛客281381469号

java实现，注意题目描述是前半部分都一样，后半部分都一样，左右两部分长度必须相等！用left和right数组分别统计左半部分的各元素出现次数和右半部分各元素出现次数，为了让左半部分都是一个字母，需要修改次数为左半部分的长度 - 左半部分统计的最大次数。同理，右半部分也是一样，最后把两者相加即可得到结果7.19
import java.util.Scanner;
import java.util.Arrays;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String s = in.nextLine();
            int mid = s.length() / 2 - 1;
            int[] left = new int[26];
            int[] right = new int[26];
            for (int i = 0; i <= mid; i++){
                left[s.charAt(i) - 'a']++;
                right[s.charAt(i + mid + 1) - 'a']++;
            }
            Arrays.sort(left);
            Arrays.sort(right);
            System.out.println((mid + 1 - left[25]) + (mid + 1 - right[25]));
        }
    }
}

发表于 2025-07-19 14:23:38 回复(0)

牛客700324568号

#include <iostream>

#include <unordered_map>

using namespace std;

int getMaxNum(string s)

{

unordered_map<char, int> umap;

for(int i=0;i<s.size();i++)

{

if(umap.find(s[i])!=umap.end()) umap[s[i]]++;

else umap[s[i]]=1;

}

int max=0;

for(auto pair:umap)

max=max>pair.second?max:pair.second;

return max;

}

int main() {

string s;

cin>>s;

cout<<s.size()-getMaxNum(s.substr(0,s.size()/2))-getMaxNum(s.substr(s.size()/2,s.size()/2))<<endl;

}

// 64 位输出请用 printf("%lld")

发表于 2025-04-09 17:10:30 回复(0)

Java

我好中意你啊

import java.util.*;

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

while (in.hasNext()) {

String str = in.nextLine();

String s1 = str.substring(0, str.length() / 2);

String s2 = str.substring(str.length() / 2);

int result = dealStr(s1) + dealStr(s2);

System.out.println(result);

}

private static int dealStr(String str) {

Map<Character, Integer> map = new HashMap<Character, Integer>();

for (int i = 0; i < str.length(); i++) {

char c = str.charAt(i);

map.put(c, map.getOrDefault(c, 0) + 1);

}

List<Integer> list = new ArrayList<>();

map.forEach((kay, value)-> {

list.add(value);

});

Collections.sort(list);

int max = list.get(list.size() - 1);

return str.length() - max;

}

发表于 2025-04-01 17:16:46 回复(0)

Java

牛客319870016号

import java.util.*;

public class Main {
    
    // 本质上就是用前半段/后半段的总长度减去出现次数最多的字符的数量
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String input = in.nextLine();
        String first = input.substring(0, input.length() / 2);
        String last = input.substring(input.length() / 2);
        Map<Character, Integer> firstMap = getMap(first);
        Map<Character, Integer> lastMap = getMap(last);
        int times = getCount(firstMap) + getCount(lastMap);
        System.out.print(times);
    }

    private static Map<Character, Integer> getMap(String str) {
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < str.length(); i++) {
            char ch = str.charAt(i);
            map.put(ch, map.getOrDefault(ch, 0) + 1);
        }
        return map;
    }

    private static int getCount(Map<Character, Integer> map) {
        if (map.size() == 1) { // 代表只有一种字母，不需要修改
            return 0;
        }
        int maxValue = 0; // 获取到出现次数最多的字符串
        int length = 0;
        for (char key : map.keySet()) {
            int value = map.get(key);
            length += value;
            if (value > maxValue) {
                maxValue = value;
            }
        }
        // 用总长度减去最多的字符串数量
        return length - maxValue;
    }
}

发表于 2025-12-09 14:42:20 回复(0)

Java

Letitgo叹服丶

import java.util.*;

public class Main {

public static void main(String[] args) {

Scanner scan = new Scanner(System.in);

String str = scan.nextLine();

if(str.length() % 2 != 0){

return;

}

String sub = str.substring(0, str.length() / 2);

String sub1 = str.substring(str.length() / 2);

Map<Character, Integer> frontMap = new HashMap<>();

Map<Character, Integer> endMap = new HashMap<>();

for (int i = 0; i < sub.length(); i++) {

frontMap.put(sub.charAt(i), frontMap.getOrDefault(sub.charAt(i), 0) + 1);

endMap.put(sub1.charAt(i), endMap.getOrDefault(sub1.charAt(i), 0) + 1);

}

int max1 = 0;

for (int i = 0; i < sub.length(); i++) {

max1 = Math.max(max1, frontMap.get(sub.charAt(i)));

}

int max2 = 0;

for (int i = 0; i < sub1.length(); i++) {

max2 = Math.max(max2, endMap.get(sub1.charAt(i)));

}

System.out.println(str.length() - max1 - max2);

}

发表于 2025-11-30 13:59:17 回复(0)

nothing5

#include <algorithm>

#include <iostream>

#include <unordered_map>

#include <string>

#include <string_view>

using namespace std;

/**

* 拆半大小为int num = s.size()，每一半的字符及其出现的个数放在unordered_map中；

* 每一半数量num/2减去最多字符数量，两半相加；

int solve(string s) {

unordered_map<char, int> first_map; //存放前半字符及出现的次数

unordered_map<char, int> second_map;//存放后半字符及出现的次数

size_t num_size = s.size();

for (int i = 0; i < num_size; i++) {

if(i < num_size / 2) {

first_map[s[i]]++;

}else {

second_map[s[i]]++;

}

int sum = 0;

sum = num_size/2 - min_element(first_map.begin(), first_map.end(), [](auto it1, auto it2){

return it1.second > it2.second ;

})->second;

sum += (num_size/2 - min_element(second_map.begin(), second_map.end(), [](auto it1, auto it2){

return it1.second > it2.second ;

})->second);

return sum;

}

int main() {

ios::sync_with_stdio(false);

cin.tie(nullptr);

string s;

cin >> s;

int count_num = solve(s);

cout << count_num << endl;

}

// 64 位输出请用 printf("%lld")

发表于 2025-10-21 13:10:59 回复(0)

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)

楼兰小石头

def getMaxS(s:str):

num = 0

for a in set(s):

if s.count(a) > num:

num = s.count(a)

return num

s = input()

s_pre = s[0:int(len(s)/2)]

s_sub = s[int(len(s)/2):]

n = (len(s)/2-getMaxS(s_pre)) + (len(s)/2-getMaxS(s_sub))

print(int(n))

发表于 2025-09-10 17:38:19 回复(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)

SQL我来了

#include <stdio.h>
#include <string.h>

int main() {
    char str[300000];
    int i, j, len, lMax=0, rMax=0, sum;
    int lChar[26] = {0}, rChar[26] = {0};
    
    scanf("%s", str);
    len = (int)strlen(str);

    if(len == 1) {
        printf("1");
    }

    for(i = 0, j = len/2; i < len/2 && j<len; i++, j++) {
        lChar[str[i]-'a']++;
        rChar[str[j]-'a']++;

        lMax = lMax > lChar[str[i]-'a'] ? lMax : lChar[str[i]-'a'];
        rMax = rMax > rChar[str[j]-'a'] ? rMax : rChar[str[j]-'a'];
    }

    sum = (len/2 -lMax) + (len/2 - rMax);
    printf("%d\n", sum);

    return 0;
}

发表于 2025-08-06 19:55:55 回复(0)

菜鸟小乔

s = input()

length = len(s)

#前半段

s0 = s[:length//2] # 切片的index必须是整数，length/2结果是小数，会报错，//结果才是整数

# 后半段

s1 = s[length//2:]

# 分别找出重复率最高的字符重复的次数n，则剩余的(len/2 - n)个是需要修改的

change_num = 0

set_0 = set(s0)

n = 0

for char in set_0:

if s0.count(char) >n:

n = s0.count(char)

change_num += (length//2 -n)

set_1 = set(s1)

n = 0

for char in set_1:

if s1.count(char)>n:

n = s1.count(char)

change_num += (length//2 -n)

print(change_num)

发表于 2025-07-19 21:19:01 回复(0)

Python 3

土豆耶夫

s = input().strip()

k = len(s)//2

s1 = s[:k]

s2 = s[k:]

strs = "abcdefghijklmnopqrstuvwxyz"

lst1 = []

lst2 = []

for ele in strs:

lst1.append(s1.count(ele))

lst2.append(s2.count(ele))

m = k - max(lst1) + k - max(lst2)

print(m)

发表于 2025-07-19 17:29:00 回复(0)

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)

牛客739161472号

const rl = require("readline").createInterface({ input: process.stdin });

var iter = rl[Symbol.asyncIterator]();

const readline = async () => (await iter.next()).value;

void async function () {

// Write your code here

const str = await readline()

const n = str.length;

const left = str.slice(0, n/2)

const right = str.slice(n/2, str.length)

let leftCountStr = new Map()

let rightCountStr = new Map()

left.split('').map(item => {

let value = leftCountStr.get(item)

leftCountStr.set(item, value ? value + 1 : 1)

})

right.split('').map(item => {

let value = rightCountStr.get(item)

rightCountStr.set(item, value ? value + 1 : 1)

})

let leftArrCount = Array.from(leftCountStr.values()).sort((a, b) => a -b)

let rightArrCount = Array.from(rightCountStr.values()).sort((a, b) => a -b)

console.log(left.length - leftArrCount[leftArrCount.length -1] + (right.length - rightArrCount[rightArrCount.length-1]))

}()

发表于 2025-06-20 18:06:57 回复(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)

Python 3

def__我爱上班__

s = input()
n = int(len(s)/2)
s1 = s[:n]
s2 = s[n:]
x  = set(s1)
y  = set(s2)
max1= max([s1.count(i) for i in x])
max2= max([s2.count(j) for j in y])
p = (n-max1) + (n-max2)
print(p)

发表于 2025-06-09 11:37:34 回复(0)

Javascript

牛客928288679号

const rl = require("readline").createInterface({ input: process.stdin });

var iter = rl[Symbol.asyncIterator]();

const readline = async () => (await iter.next()).value;

void (async function () {

// Write your code here

while ((line = await readline())) {

let tokens = line.split(" ");

let a = tokens[0];

let forntStr = a.substring(0, a.length / 2);

let endStr = a.substring(a.length / 2);

if (forntStr === endStr) {

console.log(0);

}

const firstWord = forntStr.substring(0, 1);

const endWord = endStr.substring(endStr.length - 1);

let count = 0;

let mapFornt = {},

mapEnd = {};

for (let i = 0; i < forntStr.length; i++) {

//前半部分

let keys = Object.keys(mapFornt);

let forntVal = forntStr.substring(i, i + 1);

if (keys.indexOf(forntVal) === -1) {

mapFornt[forntVal] = 1;

} else {

mapFornt[forntVal] += 1;

}

//后半部分

let _keys = Object.keys(mapEnd);

let endVal = endStr.substring(i, i + 1);

if (_keys.indexOf(endVal) === -1) {

mapEnd[endVal] = 1;

} else {

mapEnd[endVal] += 1;

}

let max = 0,

k = 0,

_keys = Object.keys(mapFornt);

while (k < _keys.length) {

max = Math.max(max, mapFornt[_keys[k]]);

k++;

}

count = forntStr.length - max;

max = 0;

k = 0;

_keys = Object.keys(mapEnd);

while (k < _keys.length) {

max = Math.max(max, mapEnd[_keys[k]]);

k++;

}

count += forntStr.length - max;

console.log(count);

}

})();

发表于 2025-06-06 11:42:16 回复(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)

ading007

package main

import (
    "fmt"
)

func main() {
    var s string
    fmt.Scan(&s)
    n := len(s)
    s1 := s[:n/2]
    s2 := s[n/2:]
    set1 := make(map[rune]int)
    set2 := make(map[rune]int)
    for _, c := range s1 {
        set1[c]++
    }
    for _, c := range s2 {
        set2[c]++
    }
    max1 := maxValueInMap(set1)
    max2 := maxValueInMap(set2)
    fmt.Println(n-max1-max2)
}

func maxValueInMap(m map[rune]int) int {
    max := 0
    for _, v := range m {
        if v > max {
            max = v
        }
    }
    return max
}

发表于 2025-05-16 21:57:17 回复(0)

C++

爱吃肉的咸鱼在春招

#include <iostream>
#include <unordered_map>
using namespace std;

int main() {

    string str;
    cin >> str;

    unordered_map<char, int> urd_map_1;
    for ( int i = 0; i < str.length() / 2; i++ ) {
        urd_map_1[ str[i] ]++;
    }

    int res1 = ( *urd_map_1.begin() ).second;
    for ( auto map : urd_map_1 ) {
        if ( map.second > res1 ) {
            res1 = map.second;
        }
    }
    res1 = str.length() / 2 - res1;


    unordered_map<char, int> urd_map_2;
    for ( int i = str.length() / 2; i < str.length(); i++ ) {
        urd_map_2[ str[i] ]++;
    }
    int res2 = ( *urd_map_2.begin() ).second;
    for ( auto map : urd_map_2 ) {
        if ( map.second > res2 ) {
            res2 = map.second;
        }
    }
    res2 = str.length() / 2 - res2;

    cout << res1 + res2 << endl;


}
// 64 位输出请用 printf("%lld")

发表于 2025-05-08 01:32:10 回复(0)

提交观点

问题信息

动态规划

难度：

34条回答 37收藏 522浏览

小红的双生串

输入描述:

输出描述:

输入

输出

说明

输入

输出

说明

问题信息

热门推荐

相关试题