首页 > 试题广场 >

小红的双生串

[编程题]小红的双生串
  • 热度指数：3995 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\hspace{15pt}小红定义一个字符串是双生串，当且仅当其前半部分所有字符相同，后半部分所有字符相同。
\hspace{15pt}现在，小红拿到了一个字符串 s ，她每次操作可以修改一个字符。小红希望你求出将其修改为双生串的最小修改次数。

输入描述:
\hspace{15pt}在一行上输入一个长度为 1 \leqq {\rm len}(s) \leqq 2 \times 10^5 且为偶数，仅由小写字母构成的字符串 s，代表待修改的字符串。


输出描述:
\hspace{15pt}输出一个整数，表示将 s 修改为双生串的最小修改次数。
示例1

输入

popipa

输出

3

说明

\hspace{15pt}在这个样例中，将 s 修改为 \texttt{ 是其中一个最优解。
示例2

输入

aaaa

输出

0

说明

\hspace{15pt}在这个样例中，给定的字符串已经是双生串，不需要修改。
算法知识视频讲解
添加回答
Javascript
牛客928288679号头像 牛客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)
提交观点

问题信息

动态规划
难度：
1条回答 525浏览

热门推荐

相关试题

小红的双生串

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号