Một chuỗi là một mảng các ký tự . Và vấn đề này là sắp xếp các phần tử của chuỗi bằng chữ hoa và chữ thường thay thế.
Mô tả sự cố - Sắp xếp chuỗi chữ hoa thường thay thế, là một vấn đề trong đó chúng tôi được cung cấp một chuỗi không có thứ tự chứa các ký tự viết hoa và viết thường hỗn hợp và chúng tôi cần sắp xếp chuỗi này theo cách sao cho các ký tự chữ hoa và chữ thường được đặt ở các vị trí thay thế nhưng ở trong một cách được sắp xếp.
Hãy lấy một ví dụ để hiểu chủ đề tốt hơn,
Input : aFegrAfStRzsV Output : AaFeRfSgVrstz Explanation : Upper case characters : A F R S V Lower case characters : a e f g r s t z
Cả hai đều được sắp xếp theo cách sắp xếp nên bây giờ chúng ta có thể đặt chúng theo thứ tự thay thế.
Bây giờ, vì chúng tôi đã hiểu vấn đề. Hãy tạo ra một giải pháp cho nó. Một cách là tạo mảng cho cả chữ hoa và chữ thường theo thứ tự được sắp xếp và sau đó xen kẽ chúng trong chuỗi cuối cùng. Chúng tôi đã tạo một thuật toán dựa trên logic này.
Thuật toán
Step 1 : In an array lowercount[] add all lowercase characters in sorted order. Step 2 : In an array uppercount[] add all uppercase characters in sorted order. Step 3 : Create the final string using alternate values from both arrays. Step 4 : Print the result array.
Ví dụ
#include <iostream>
using namespace std;
#define MAX 26
void alternateULSort(string& s) ;
int main(){
string str = "aFegrAfStRzsV";
cout<<"The unsorted string is : "<<str;
cout<<"\nThe alternate lower upper sorted string is ";
alternateULSort(str);
cout << str << "\n";
}
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]--;
}
}
} Đầu ra
The unsorted string is : aFegrAfStRzsV The alternate lower upper sorted string is AaFeRfSgVrstz