การจัดเรียงสตริงสลับตัวพิมพ์ใหญ่-เล็ก (Alternate Lower Upper Sort) ใน C++

บทนำ

จัดเรียงสตริงที่มีตัวพิมพ์ใหญ่และเล็กผสมกัน ให้เรียงตัวพิมพ์ใหญ่แยกกัน ตัวพิมพ์เล็กแยกกัน แล้วนำมารวมกันสลับกัน

ตัวอย่าง

Input: "aFegrAfStRzsV"

Uppercase สorted: A, F, R, S, V

Lowercase สorted: a, e, f, g, r, s, t, z

Output: "AaFeRfSgVrstz" (สลับ Upper-Lower)

อัลกอริทึม

1. นับความถี่ตัวพิมพ์ใหญ่ (upperCount[26]) และตัวพิมพ์เล็ก (lowerCount[26])
2. สร้างสตริงผลลัพธ์โดยสลับ: เอาตัวพิมพ์ใหญ่ตัวถัดไป → ตัวพิมพ์เล็กตัวถัดไป → ซ้ำจนครบ

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

#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 << "Unsorted: " << str << "\nSorted: ";
    alternateULSort(str);
    cout << str << "\n";
    return 0;
}

ผลลัพธ์

The unsorted string is: aFegrAfStRzsV
The alternate lower upper sorted string is AaFeRfSgVrstz