C++ 按字典顺序排列的字符串

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

问题描述 - 我们给定一个包含字母字符的字符串alpha。我们需要构建一个按字典顺序最小的字符串，通过将任意字符串前缀与其反转连接起来。

示例示例

输入

alpha = "welcome";

输出

'wewe’

解释 - 字典序最小的前缀是“we”。因此，我们将其与其镜像连接起来。

输入

alpha = "tutorialspoint"

输出

‘tt’

解释 - ‘tu’大于‘t’，所以所有其他前缀也会大于‘tu’。

输入

alpha = "edcba";

输出

edcbaabcde

说明： 该字符串的所有字符都按降序排列。因此，我们将整个字符串作为前缀，并将其与其反转合并。

方法一

在这个方法中，我们将遍历字符串，直到找到包含按降序排列的字符的前缀。然后，我们将与其反转拼接以获得按字典顺序最小的字符串。

算法

步骤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;
}