Sắp xếp chuỗi chữ hoa chữ thường xen kẽ trong C++

Cho chuỗi chứa ký tự hoa và thường. Sắp xếp sao cho chữ hoa và chữ thường xen kẽ nhau, mỗi nhóm được sắp xếp tăng dần.

Ví dụ: "aFegrAfStRzsV" -> Chữ hoa: A,F,R,S,V; Chữ thường: a,e,f,g,r,s,t,z -> Kết quả: AaFeRfSgVrstz.

Thuật toán:

1. Đếm tần suất 26 chữ hoa (upperCount) và 26 chữ thường (lowerCount).
2. Duyệt 2 mảng đếm, lấy ký tự còn count > 0, điền luân phiên vào chuỗi kết quả.

Ví dụ code

#include <iostream>
using namespace std;
#define MAX 26

void alternateULSort(string& s) {
    int n = s.length();
    int lowerCount[MAX] = {0}, upperCount[MAX] = {0};
    for (int i = 0; i < n; i++) {
        if (isupper(s[i])) upperCount[s[i]-'A']++;
        else lowerCount[s[i]-'a']++;
    }
    int i = 0, j = 0, k = 0;
    while (k < n) {
        while (i < MAX && upperCount[i] == 0) i++;
        if (i < MAX) { s[k++] = 'A' + i; upperCount[i]--; }
        while (j < MAX && lowerCount[j] == 0) j++;
        if (j < MAX) { s[k++] = 'a' + j; lowerCount[j]--; }
    }
}

int main() {
    string str = "aFegrAfStRzsV";
    cout << "Chuoi goc: " << str << endl;
    alternateULSort(str);
    cout << "Chuoi sap xep: " << str << endl;
    return 0;
}

Kết quả

Chuoi goc: aFegrAfStRzsV
Chuoi sap xep: AaFeRfSgVrstz