โค้ด C++ หาสองสตริงย่อยมีหนึ่งสตริงน้อยสุด

สมมติว่าเรามีสตริง S ตัวพิมพ์เล็ก n ตัวอักษร ต้องหาสตริงย่อย P และ Q ไม่ว่าง ที่:

• P และ Q เป็น subsequence ของ S
• สำหรับทุก i, S[i] อยู่ใน P หรือ Q เพียงอย่างใดอย่างหนึ่ง
• P เป็น lexicographically minimum ที่สุด

เช่น ถ้าอินพุตคือ S = "thelightsaber" เอาต์พุตจะเป็น 10...

ขั้นตอนการแก้ปัญหา

c := S
เรียงลำดับ c
a := ตำแหน่งของ c[0] ใน S
ลบ c ออกจาก S
print c[0] และ S

ตัวอย่างโค้ด

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

void solve(string S) {
    string c = S;
    sort(c.begin(), c.end());
    int a = S.find(c[0]);
    S.erase(S.begin() + a);
    cout << c[0] << ", " << S << endl;
}

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

อินพุต

"thelightsaber"

เอาต์พุต

a, thelightsber