Count the number of pairs

While solving problems from Codeforces, I came across a problem called “Count the number of pairs”. She is from level 1000. Let’s look at her solution principle together.

The condition of our task:

Christina has a string s of length n, consisting only of lowercase and uppercase Latin letters. For each pair of a lowercase letter and its corresponding capital letter, Christina can receive 1 ruble. At the same time, pairs of symbols cannot intersect, that is, each symbol can only be in one pair.

For example, if she has the string s = “aAaaBACacbE”, then she can receive a ruble for the following pairs of characters:

s1 = “a” and s2 = “A”
s4 = “a” and s6 = “A”
s5 = “B” and s10 = “b”
s7 = “C” and s9 = “c”

Christina wants to get more rubles for her string, so she is going to perform no more than k operations on it. In one operation she can:

or select the lowercase symbol si (1≤i≤n1) and make it uppercase.
or select the uppercase symbol si (1≤i≤n1) and make it lowercase.

For example, with k = 2 and s = “aAaaBACacbE” she can perform one operation: select s3 = “a” and make it capital. Then she will receive another pair of s3 = “A” and s8 = “a”.

Find the maximum number of rubles that Christina can receive for her line.

The condition is quite easy, let’s move on to the solution right away.

Let’s write the code in C++:

#include <iostream>
#include <cstring> 
using namespace std;

const int N = 26;

void word() {
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;

    int big[N] = {0}; //array for counting the number of capital letters
    int small[N] = {0}; //array for counting the number of lowercase letters

    //count the number of uppercase and lowercase letters in a stringminimum between the available number of operations and half of the remaining letters
    for (char ch : s) {
        if ('A' <= ch && ch <= 'Z') big[ch - 'A']++;
        else small[ch - 'a']++;
    }

    int answer = 0; //variable to store the response

    //count the number of pairs of letters that can be formed
    for (int i = 0; i < N; ++i) {
        int pairs = min(small[i], big[i]); //minimum of the number of lowercase and uppercase letters of the current letter
        answer += pairs; //increase the total number of pairs

        //reduce the number of remaining letters by the number of pairs formed
        small[i] -= pairs;
        big[i] -= pairs;

        //use the remaining operations to increase the number of pairs
        int add = min(k, max(small[i], big[i]) / 2); //minimum between the available number of operations and half of the remaining letters
        k -= add; //reduce the number of available operations
        answer += add; //increase the total number of pairs
    }

    cout << answer << endl; //display the answer
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        word();
    }
    return 0;
}

We create two arrays “big” and “small” of length N = 26, since there are only 26 Latin letters.

The “for” loop loops through each ch character in the string s. If the character is a capital letter (‘A’ <= ch && ch <= ‘Z’), the array element “big” is incremented. If the character is a lowercase letter (‘a’ <= ch && ch <= ‘z’), the array element small is incremented.

We solved the problem “Count the number of pairs”!))