通过连接任何前缀及其镜像形式形成的字典序最小字符串

---

在这个问题中，我们将通过连接给定字符串的前缀及其反转形式来找到字典序最小的字符串。我们可以找到字符串的字典序最小的前缀并获得所需的字符串。

问题陈述 – 我们得到一个包含字母字符的字符串 alpha。我们需要构造字典序最小的字符串，该字符串可以通过连接任何字符串前缀及其反转形式来获得。

示例

输入

alpha = "welcome";

输出

'wewe’

解释 – 字典序最小的前缀是“we”。所以，我们将它与其镜像连接。

输入

alpha = "tutorialspoint"

输出

‘tt’

解释 – “tu”大于“t”，所以所有其他前缀也大于“tu”。

输入

alpha = "edcba";

输出

edcbaabcde

解释 – 字符串的所有字符都是递减顺序排列的。所以，我们取整个字符串作为前缀并将其与反转形式合并。

方法 1

在这种方法中，我们将遍历字符串，直到找到包含递减顺序字符的前缀。之后，我们将与它的反转形式连接以获得字典序最小的字符串。

算法

步骤 1 – 使用字符串的第一个字符初始化“preStr”字符串变量以存储字典序最小的前缀。

步骤 2 – 开始迭代字符串。

步骤 3 – 在循环中，如果第 p 个索引处的字符在字典序上小于“preStr”字符串的最后一个字符，则将该字符追加到“preStr”字符串。

步骤 4 – 如果字符与“preStr”字符串的最后一个字符相同，并且“preStr”字符串的大小大于 1，则将该字符追加到“preStr”。

步骤 5 – 在所有其他情况下，中断循环。

步骤 6 – 将“preStr”字符串存储在“temp”字符串变量中并将其反转。

步骤 7 – 连接“preStr”和“temp”字符串后返回结果字符串。

示例

#include <bits/stdc++.h>
using namespace std;

string getString(string alpha) {
    // To store the prefix string
    string preStr = "";
    // Initialization
    preStr += alpha[0];
    // Iterate the string
    for (int p = 1; p < alpha.length(); p++) {
        // Get largest prefix string in decreasing order
        if (alpha[p] < preStr.back()) {
            preStr += alpha[p];
        } else if (alpha[p] == preStr.back() && preStr.size() > 1) {
            preStr += alpha[p];
        } else {
            break;
        }
    }
    // Do reverse of string
    string temp = preStr;
    reverse(temp.begin(), temp.end());
    // Final answer
    return preStr + temp;
}
int main() {
    string alpha = "welcome";
    cout << "The output string is - " << getString(alpha);
    return 0;
}

输出

The output string is - weew

时间复杂度 – O(N) 用于查找字典序最小的前缀。

空间复杂度 – O(N) 用于存储结果字符串。

如果我们取任何其他前缀而不是字典序最小的前缀，我们无法通过连接前缀及其反转形式来构造字典序最小的字符串。程序员可以尝试解决我们需要通过连接给定字符串的任何子串或子序列来构造字典序最小的字符串的问题。