C++: 最少删除字符使字符串左移和右移相同

题目描述

对于一个字符串't[1],t[2],...,t[n]'，我们定义它的右移为 't[n],t[1],...,t[n-1]'；我们定义它的左移为 't[2],t[3],...,t[n],t[1]'。

现在请问对于给出的一个字符串，最少删掉多少个字符才能是这个字符串的左移和右移完全相同？

注意：题目保证字符串中的所有字符都是数字，'t[x]' 属于 '[0,1,2,3,4,5,6,7,8,9]'。

输入格式

输入共一行一个字符串 's', 表示给定字符串，'s[i]' 属于 '[0,1,2,3,4,5,6,7,8,9]'。

输出格式

输出一个整数，代表最少删掉多少个字符才能是这个字符串的左移和右移完全相同。

输入

100120013

输出

数据范围

对于 50% 的数据，有 1 <= abs(s) <= 10^3。对于 100% 的数据，有 2 <= abs(s) <= 2*10^5。

解题思路：

我们可以从左边或者右边开始删除字符，直到字符串左移和右移完全相同。

首先，我们需要找到字符串中所有出现的数字，然后计算每个数字在字符串中出现的次数。

接下来，我们可以遍历字符串，对于每个字符，我们可以选择删除它或者保留它。

如果我们删除一个字符，那么对应的数字出现的次数减少 1。

我们可以维护两个数组 'left' 和 'right'，其中 'left[i]' 表示在字符串左移 'i' 位后，每个数字出现的次数，'right[i]' 表示在字符串右移 'i' 位后，每个数字出现的次数。

我们可以通过遍历字符串，更新 'left' 和 'right' 数组，计算出每个数字在字符串左移和右移后的出现次数。

然后，我们可以遍历 'left' 和 'right' 数组，对于每个数字，我们可以计算删除字符的最小次数。

最终的答案就是所有数字删除字符的最小次数的总和。

具体实现：

遍历字符串，统计每个数字出现的次数。
初始化 'left' 和 'right' 数组，将 'left[0]' 和 'right[0]' 初始化为字符总数。
遍历字符串，更新 'left' 和 'right' 数组。
- 对于每个字符，将它对应的数字出现次数减 1。
- 更新 'left[i]' 和 'right[i]'，根据 'left[i-1]' 和 'right[i-1]' 以及当前字符对应的数字出现次数。
遍历 'left' 和 'right' 数组，计算删除字符的最小次数。
输出最小次数的总和作为答案。

C++ 代码实现如下：

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int solve(string s) {
    vector<int> count(10, 0); // 统计每个数字出现的次数
    for (char c : s) {
        count[c - '0']++;
    }

    int n = s.size();
    vector<int> left(n+1, 0); // 左移i位后，每个数字出现的次数
    vector<int> right(n+1, 0); // 右移i位后，每个数字出现的次数
    left[0] = n;
    right[0] = n;

    for (int i = 1; i <= n; i++) {
        int num = s[i-1] - '0';
        count[num]--;
        left[i] = left[i-1] - count[num];
        right[i] = right[i-1] - count[num];
    }

    int ans = n;
    for (int i = 1; i <= n; i++) {
        ans = min(ans, left[i] + right[n-i]);
    }
    return ans;
}

int main() {
    string s;
    cin >> s;
    int ans = solve(s);
    cout << ans << endl;
    return 0;
}

时间复杂度分析：

遍历字符串统计数字出现次数的时间复杂度为 O(n)。遍历字符串更新 'left' 和 'right' 数组的时间复杂度为 O(n)。遍历 'left' 和 'right' 数组计算删除字符的最小次数的时间复杂度为 O(n)。所以总的时间复杂度为 O(n)。其中，n 为字符串的长度。