目录

一、题目内容

二、解题思路

三、代码

一、题目内容

给定一个字符串S，检查是否能重新排布其中的字母，使得两相邻的字符不同。

若可行，输出任意可行的结果。若不可行，返回空字符串。

示例 1:

输入: S = "aab"
输出: "aba"

示例 2:

输入: S = "aaab"
输出: ""

注意:

S 只包含小写字母并且长度在[1, 500]区间内。

二、解题思路

1.对S中的字母构建数组哈希表，统计各个字符出现的次数；

2.将出现次数最多的字符，添加至res结果字符串，并且次数减一；

3.每次循环都去找当前出现次数最多，并且和上一个添加进res中不同的字符，插入到结果字符串后；

4.如果找不到这样的字符，就返回“”空字符串

注：若想得到相邻这样的关系，只有字母出现次数多的相邻，否则只能一个挨着一个都是一样的字母了。

三、代码

      class Solution:
      def reorganizeString(self, S: str) -> str:
       record = [0 for _ in range(26)]
      for i in range(len(S)):
       record[ord(S[i]) - ord('a')] += 1
       max_record = max(record)
       max_record_index = record.index(max_record)
       res = []
       res.append(chr(ord('a') + max_record_index))
       record[max_record_index] -= 1
      while len(res) < len(S):
       next_max_record_index = -1
       max_record = 0
      for i in range(26):
      if record[i] > max_record and i != max_record_index:
       max_record = record[i]
       next_max_record_index = i
      if next_max_record_index != -1:
       res.append(chr(ord('a') + next_max_record_index))
       record[next_max_record_index] -= 1
       max_record_index = next_max_record_index
      else:
      return ""
      return "".join(res)
      if __name__ == '__main__':
       a = "aaab"
       s = Solution()
       ans = s.reorganizeString(a)
       print(ans)
  
 

文章来源: nickhuang1996.blog.csdn.net，作者：悲恋花丶无心之人，版权归原作者所有，如需转载，请联系作者。

原文链接：nickhuang1996.blog.csdn.net/article/details/110384725