Maximal Char Requests
In this challenge, a string and a list of intervals are given. The string consists of English letters only and it can contain both lowercase and uppercase letters.
For two different letters, we say that the first letter is greater than the second letter when the first letter comes later in the alphabet than the second letter ignoring the case of the letters. For example, the letter 'Z' and 't' are greater than the letters 'b' and 'G', while the letters 'B' andd 'b' are equal as case is not considered.
The task is the following. For each given interval, you need to find the count of the greatest letter occurring in the string in that interval, ignoring the case of the letters, so occurrences of, for example, and are occurrences of the same letter.
Consider, for example, for the string "AbaBacD". In the interval, [0, 4], the greatest letter is 'b' with count 2.
Input Format
The first line contains integer , denoting the length of the input string.
The second line contains string .
The third line contains an integer , denoting the number of intervals. Each line of the subsequent lines contains two space-separated integers and , denoting the beginning and the end of interval.
Constraints
Subtasks
For of the maximum score.
Output Format
For each interval, print the count of the greatest letter occurring in the string in that interval.
Sample Input 0
5
ddaaa
1
0 4
Sample Output 0
2
Explanation 0
The string is "ddaaa" and there is only one interval, i.e. the interval denoting the whole string. The greatest character occuring in that interval is and its count is , therefore, is the answer.
Sample Input 1
8
aAabBcba
5
2 6
1 2
2 2
0 4
0 7
Sample Output 1
1
2
1
2
1
Explanation 1
The input string is "aAabBcba" and there are 5 intervals to check:
- -> aA[abBcb]a -> '' is the greatest and occurs time
- -> a[Aa]bBcba -> '' is the greatest and occurs times
- -> aA[a]bBcba -> '' is the greatest and occurs time
- -> [aAabB]cba -> '' is the greatest and occurs times
- -> [aAabBcba] -> '' is the greatest and occurs time
xxxxxxxxxx
char* readline();
char* ltrim(char*);
char* rtrim(char*);
char** split_string(char*);
int parse_int(char*);
/*
* Complete the 'getMaxCharCount' function below.
*
* The function is expected to return an INTEGER_ARRAY.
* The function accepts following parameters:
* 1. STRING s
* 2. 2D_INTEGER_ARRAY queries
*/
/*
* To return the integer array from the function, you should:
* - Store the size of the array to be returned in the result_count variable
* - Allocate the array statically or dynamically
*
* For example,
* int* return_integer_array_using_static_allocation(int* result_count) {
* *result_count = 5;
*
* static int a[5] = {1, 2, 3, 4, 5};
*
* return a;
* }
*
* int* return_integer_array_using_dynamic_allocation(int* result_count) {
* *result_count = 5;
*
* int *a = malloc(5 * sizeof(int));
*
* for (int i = 0; i < 5; i++) {
* *(a + i) = i + 1;
* }
*
* return a;
* }
*
*/
int* getMaxCharCount(char* s, int queries_rows, int queries_columns, int** queries, int* result_count) {
// queries is a n x 2 array where queries[i][0] and queries[i][1] represents x[i] and y[i] for the ith query.
}
int main()
{
FILE* fptr = fopen(getenv("OUTPUT_PATH"), "w");
int n = parse_int(ltrim(rtrim(readline())));
char* s = readline();
int q = parse_int(ltrim(rtrim(readline())));
int** query = malloc(q * sizeof(int*));
for (int i = 0; i < q; i++) {
*(query + i) = malloc(2 * (sizeof(int)));
char** query_item_temp = split_string(rtrim(readline()));
for (int j = 0; j < 2; j++) {
int query_item = parse_int(*(query_item_temp + j));
*(*(query + i) + j) = query_item;
}
}
int ans_count;
int* ans = getMaxCharCount(s, q, 2, query, &ans_count);
for (int i = 0; i < ans_count; i++) {
fprintf(fptr, "%d", *(ans + i));
if (i != ans_count - 1) {
fprintf(fptr, "\n");
}
}
fprintf(fptr, "\n");
fclose(fptr);
return 0;
}
char* readline() {
size_t alloc_length = 1024;
size_t data_length = 0;
char* data = malloc(alloc_length);
while (true) {
char* cursor = data + data_length;
char* line = fgets(cursor, alloc_length - data_length, stdin);
if (!line) {
break;
}
data_length += strlen(cursor);
if (data_length < alloc_length - 1 || data[data_length - 1] == '\n') {
break;
}
alloc_length <<= 1;
data = realloc(data, alloc_length);
if (!data) {
data = '\0';
break;
}
}
if (data[data_length - 1] == '\n') {
data[data_length - 1] = '\0';
data = realloc(data, data_length);
if (!data) {
data = '\0';
}
} else {
data = realloc(data, data_length + 1);
if (!data) {
data = '\0';
} else {
data[data_length] = '\0';
}
}
return data;
}
char* ltrim(char* str) {
if (!str) {
return '\0';
}
if (!*str) {
return str;
}
while (*str != '\0' && isspace(*str)) {
str++;
}
return str;
}
char* rtrim(char* str) {
if (!str) {
return '\0';
}
if (!*str) {
return str;
}
char* end = str + strlen(str) - 1;
while (end >= str && isspace(*end)) {
end--;
}
*(end + 1) = '\0';
return str;
}
char** split_string(char* str) {
char** splits = NULL;
char* token = strtok(str, " ");
int spaces = 0;
while (token) {
splits = realloc(splits, sizeof(char*) * ++spaces);
if (!splits) {
return splits;
}
splits[spaces - 1] = token;
token = strtok(NULL, " ");
}
return splits;
}
int parse_int(char* str) {
char* endptr;
int value = strtol(str, &endptr, 10);
if (endptr == str || *endptr != '\0') {
exit(EXIT_FAILURE);
}
return value;
}