Tìm hai xâu con P,Q phân hoạch S sao cho P nhỏ nhất theo từ điển bằng C++

Mô tả bài toán

Cho chuỗi S. Tìm P,Q không rỗng, hợp nhất thành S (mỗi ký tự thuộc đúng một trong P,Q), P là dãy con của S, Q là dãy con của S, P nhỏ nhất theo từ điển.

Ví dụ

S="thelightsaber" → Output: "a", "thelightsber" (P="a" là nhỏ nhất).

Thuật toán

P nhỏ nhất là ký tự nhỏ nhất trong S. Lấy ký tự nhỏ nhất đầu tiên làm P, phần còn lại làm Q.

Code C++

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

void solve(string S) {
    string sorted = S;
    sort(sorted.begin(), sorted.end());
    char minChar = sorted[0];
    size_t pos = S.find(minChar);
    string Q = S.substr(0, pos) + S.substr(pos+1);
    cout << minChar << ", " << Q << endl;
}

int main() {
    string S = "thelightsaber";
    solve(S);
    return 0;
}

Đầu vào / Đầu ra

Input: "thelightsaber"

Output: a, thelightsber