首页 > 试题广场 >

小红的字符串构造

[编程题]小红的字符串构造
  • 热度指数:3210 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
小红拿到了一个字符串s,她准备构造一个和s长度相同的字符串t:满足以下条件:
1. t的字符集和s的相同(去重后的,也就是说不考虑数量)
2. t的每个位置的字符都和s不同。
例如若 s="aabbc",那么t可以构造为"cbaca"。
你能帮帮小红吗?

输入描述:
输入一个仅由小写字母组成的字符串s,长度不超过 200000。


输出描述:
如果无解,请输出 -1。
否则输出任意合法的字符串。
示例1

输入

aabbc

输出

cbaca

说明

"bcacb"等字符串也是合法的构造。
# 将输入字符串转换为字符列表
s = list(input())

# 初始化用于存储转换后字符的列表
t = []

# 初始化用于跟踪输入字符串中唯一字符的列表
char_set = []

# 初始化用于存储字符到字符映射的字典
char_map = {}

# 遍历输入字符串中的每个字符
for i in s:
    # 如果字符不在char_set中,则将其添加进去
    if i not in char_set:
        char_set.append(i)

# 检查char_set中的字符数量
# 如果少于2个字符,则无法进行有效的映射,输出-1
if len(char_set) < 2:
    print(-1)
else:
    # 创建字符到字符的映射
    for i in range(len(char_set)):
        # 如果是最后一个字符,则将其映射回第一个字符,形成循环
        if i == (len(char_set) - 1):
            char_map[char_set[i]] = char_set[0]
        else:
            # 否则,将字符映射到下一个字符
            char_map[char_set[i]] = char_set[i + 1]

    # 应用映射到输入字符串中的每个字符
    for i in s:
        # 使用char_map将字符转换为其映射字符,并添加到结果列表t中
        t.append(char_map[i])

    # 将结果列表t中的字符连接成一个字符串并打印
    print("".join(t))

发表于 2025-01-21 09:50:55 回复(0)