首页 > 试题广场 >

小红的双生串

[编程题]小红的双生串

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

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

输入描述:

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

输出描述:

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

示例1

输入

popipa

输出

说明

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

示例2

输入

aaaa

输出

说明

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

算法知识视频讲解

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)