首页 > 试题广场 >

小红的字符串构造

[编程题]小红的字符串构造

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

小红拿到了一个字符串 $s$ ，她准备构造一个和 $s$ 长度相同的字符串 $t$ ：满足以下条件：
1. $t$ 的字符集和 $s$ 的相同（去重后的，也就是说不考虑数量）
2. $t$ 的每个位置的字符都和 $s$ 不同。
例如若 s="aabbc"，那么 $t$ 可以构造为"cbaca"。
你能帮帮小红吗？

输入描述:

输入一个仅由小写字母组成的字符串，长度不超过 200000。

输出描述:

如果无解，请输出 -1。
否则输出任意合法的字符串。

示例1

输入

aabbc

输出

cbaca

说明

"bcacb"等字符串也是合法的构造。

算法知识视频讲解

Mag1c0nch

发表于 2024-11-19 16:42:23

我们先分别讨论两个限制条件，提炼出其中的信息t和s字符集相同，代表s中出现的所有字符在t中都有出现t的每个位置的字符都和s不同，代表t[i] != s[i]观察样例我们发现构造方法很多，但是我们需要写出一种简单的，普适的方法，对于aabbc这种情况，我们可以发现，我们可以将s中的所有a全部变成c，所展开全文

kkkyd

发表于 2024-11-19 19:51:10

#include <bits/stdc++.h> using namespace std; int main() { string s; cin>>s; unordered_map<char,bool>p;//记录出现字符 uno 展开全文

welken

发表于 2024-11-19 18:46:03

强调这题没有对数量作要求，比如abbcde，我们取下一个字母，即bccdea满足题意。我们考虑用usechar存储字符集，把字符集存到vector数组方便管理。随后我们考虑用lower_bound找到字符串中每一个字符s[i]在distinct_chars的位置，仅需让迭代器+1，就得到了下展开全文

牛牛队_

发表于 2024-11-20 21:13:49

#include <bits/stdc++.h> using namespace std; int __t = 1, n; void solve() { string s; cin >> s; map <char,char> m; 展开全文

谢特123

发表于 2024-11-20 22:13:26

#include <bits/stdc++.h> #include <unordered_map> #include <unordered_set> using namespace std; string ss(string s) { unordered_ 展开全文

呆呆呆呆鸟

发表于 2024-11-19 22:49:56

思路：凯撒密码。收集字符串 s 里出现的字母，用 set 默认排序，得到 abcd......使字母偏移一位即可，a->b, b->c, c->d, ......, z->a 再遍历字符串 s，替换 s 的字母即可 #include<bits/stdc++.h> 展开全文

Kato_Shoko

发表于 2024-11-19 16:01:21

需要先填一遍字母，保证集合一样，使用map来匹配比较简单 #include <iostream> #include <queue> #include <map> #include <set> #include <cmath> #includ 展开全文

在提需求的海螺很想退休

发表于 2024-11-19 16:21:36

#include <iostream> #include <string> #include <set> #include <algorithm> using namespace std; string s; int main() { c 展开全文

whiteg

发表于 2024-11-19 16:51:10

s = list(input()) n = len(s) dic = sorted(set(s)) t = [-1]*n s1 = len(dic) for i in range(n): t[i] = dic[(dic.index(s[i]) + 1)%s1] if s1 > 1: 展开全文

Feijoa_Li

发表于 2024-11-19 17:29:06

分析题目1、目标字符数组需要包含原数组所有出现过的字母2、目标数组任意位置与原数组不同因此我们考虑直接根据原数组来构建新数组考虑任意位置与原数组不同，我们将a的位置转到的b的位置（如果b在原数组出现过）若b从未出现，那么顺位下去c、d、e...直到有一个字母出现过然后b的位置再转移到下一个字母的位置展开全文