题目地址:
https://leetcode-cn.com/problems/increasing-decreasing-string/
给你一个字符串 s ,请你根据下面的算法重新构造字符串:
请你返回将 s 中字符重新排序后的 结果字符串 。
示例 1:
输入:s = "aaaabbbbcccc"
输出:"abccbaabccba"
解释:第一轮的步骤 1,2,3 后,结果字符串为 result = "abc"
第一轮的步骤 4,5,6 后,结果字符串为 result = "abccba"
第一轮结束,现在 s = "aabbcc" ,我们再次回到步骤 1
第二轮的步骤 1,2,3 后,结果字符串为 result = "abccbaabc"
第二轮的步骤 4,5,6 后,结果字符串为 result = "abccbaabccba"
示例 2:
输入:s = "rat"
输出:"art"
解释:单词 "rat" 在上述算法重排序以后变成 "art"
示例 3:
输入:s = "leetcode"
输出:"cdelotee"
示例 4:
输入:s = "ggggggg"
输出:"ggggggg"
示例 5:
输入:s = "spo"
输出:"ops"
提示:
1 <= s.length <= 500
s 只包含小写英文字母。
思路:
题目意思还是比较明确的,基于原始的字符串,从中先找上升的字符串,然后再从剩余的字符串中找最大的下降字符串,拼接起来循环下去。最终输出长度等于输入长度,原始字符串中每个字符的个数等于输出字符串中每个字符的个数,仔细分析步骤,我们发现:
class Solution:
def sortString(self, s: str) -> str:
num = [0] * 26
for ch in s:
num[ord(ch) - ord('a')] += 1 # 统计每个字符出现个数
ret = []
while len(ret) != len(s): # 如果输出长度等于输出输入长度,结束循环
# 先找最小上升字符串
for i in range(26):
if num[i]:
ret.append(chr(i + ord('a')))
num[i] -= 1
# 再找最大下降
for i in range(25, -1, -1):
if num[i]:
ret.append(chr(i + ord('a')))
num[i] -= 1
return ''.join(ret)