Java 中字典序最小的回文串

给定一个字符串 "str"，我们的任务是通过重新排列给定文本中的字符来创建一个字典序最小的回文串。如果不存在这样的字符串，则返回消息 "不存在这样的回文串"。

示例 1

输入

字符串 str = "madam"

输出

字典序最小的回文串是 amdma。

解释

对于给定的字符串 "madam"，字符的字典序是 {a, d, m}。因此，我们将用第一个字符 'i' 来形成回文串。因此，可以形成的第一字典序回文串是 "amdma"。

示例 2

输入

字符串 str = "mississippi"

输出

字典序最小的回文串是 iipssmsspii。

解释

对于给定的字符串 "mississippi"，字符的字典序是 {i, m, p, s}。因此，我们将用第一个字符 'i' 来形成回文串。因此，可以形成的第一字典序回文串是 "iipssmsspii"。

示例 3

输入

字符串 str = "sis"

输出

不存在这样的回文串。

解释

对于给定的字符串 "sis"，字符的字典序是 {i, s, s}。尽管给定的字符串按字典序排列时是一个回文串，但该字符串无法构成回文串。因此，不存在这样的回文串。

方法：高效方法

该方法找到的回文串特别遵循两个属性：1. 如果字符串长度是偶数，则字符串中的每个字符必须出现偶数次。2. 如果长度是奇数，则应该有一个字符出现奇数次，所有其他字符出现偶数次，并且奇数字符至少出现在字符串的中心一次。

算法

步骤 1： 创建 countingFrequency 函数，用于计算输入字符串中每个字符的频率。

步骤 2： 声明一个名为 palindrome 的函数，用于检查输入字符串的字符是否可以用于创建回文串。

步骤 3： 初始化 OddFrequency 函数，用于识别并减少输入字符串中奇数字符的频率。

步骤 4： 要从输入字符串创建字典序最小的回文串，请创建主函数 PalindromicString。

步骤 4.1： 在 PalindromicString 中使用 countingFrequency 来确定每个字符的频率。

步骤 5： 通过单词的结构检查是否可以形成回文串。

步骤 6： 使用 OddFrequency 来定位并（如果可能）减少奇数字符的频率。

步骤 7： 通过按升序组合字符来创建回文串的前端和后端。

步骤 8： 返回字典序最小的回文串。

实施

文件名： LexicographFirstPalindrome.java

输出

The lexicographic first palindromic string is: amdma

复杂度分析

上述代码的时间复杂度为 O(N)，空间复杂度为 O(N)，其中 N 代表字符串的长度。