题解 | #字符串排序#

import sys
# 在这个问题中，非alpha字符相当于一个隔断
#那么首先挑选出非alpha字符部分，然后进行排序，值得注意的是
#需要处理大小写，那么在重组时要考虑，原字母的初始索引进行同字母的排序
#再重组过程中索引和非alpha字符一样时，直接输入字符，然后再下一步
#感觉用动态规划会好一些，找到最长顺序和逆序序列，然后总序列长-（顺+逆）就是要剔除的
def HJ26_sort(s):
    # 获取所有的字母和它们的索引
    letters_with_indices = [(char, idx) for idx, char in enumerate(s) if char.isalpha()]

    # 分离字母和非字母字符
    non_letters = [char for char in s if not char.isalpha()]
    
    # 按规则对字母进行排序
    sorted_letters = sorted(letters_with_indices, key=lambda x: (x[0].lower(), x[1]))

    # 重新组合字符串并保持非字母字符位置不变
    result = ''
    pointer = 0
    for char in s:
        if char.isalpha():
            result += sorted_letters[pointer][0]
            pointer += 1
        else:
            result += char

    return result

string = input()
print(HJ26_sort(string))