透過連線任何字首及其映象形式形成的字典序最小字串

---

在這個問題中，我們將透過連線給定字串的字首及其反轉形式來找到字典序最小的字串。我們可以找到字串的字典序最小的字首並獲得所需的字串。

問題陳述 – 我們得到一個包含字母字元的字串 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) 用於儲存結果字串。

如果我們取任何其他字首而不是字典序最小的字首，我們無法透過連線字首及其反轉形式來構造字典序最小的字串。程式設計師可以嘗試解決我們需要透過連線給定字串的任何子串或子序列來構造字典序最小的字串的問題。