Kiểm tra chuỗi có thể phá vỡ chuỗi khác (Check If a String Can Break Another String) trong C++

Cho hai chuỗi s1, s2 cùng độ dài. Chuỗi a "phá vỡ" (can break) chuỗi b nếu sau khi sắp xếp, a[i] >= b[i] ∀i. Kiểm tra xem có hoán vị của s1 phá vỡ hoán vị của s2 hoặc ngược lại không.

Ví dụ

Đầu vào: s1 = "abc", s2 = "xya"
Đầu ra: true (sắp xếp: "abc" và "axy", "axy" phá vỡ "abc").

Thuật toán

1. Sắp xếp cả hai chuỗi.
2. Kiểm tra s1 >= s2 (từng ký tự) hoặc s2 >= s1.
3. Trả về true nếu một trong hai đúng.

Triển khai C++

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

class Solution {
    bool check(const string& a, const string& b) {
        for (int i = 0; i < a.size(); ++i)
            if (a[i] < b[i]) return false;
        return true;
    }
public:
    bool checkIfCanBreak(string s1, string s2) {
        sort(s1.begin(), s1.end());
        sort(s2.begin(), s2.end());
        return check(s1, s2) || check(s2, s1);
    }
};

Độ phức tạp

• Thời gian: O(N log N) do sắp xếp.
• Không gian: O(1) thêm (sắp xếp in-place).

Kết quả kiểm thử

Đầu vào: "abc", "xya"
Đầu ra: 1 (true)