Parity in the number of letters with the same letter position and frequency parity

In this problem we will count the number of characters with same parity in frequency and position and print the count of that number as odd or even.

To solve this problem, we can find the frequency of each character in the string and count the total number of characters with the same parity in frequency and position. After that we can print odd or even answers based on the count.

Problem Statement - We are given a string alpha containing only lowercase English alphabetic characters. We need to check if the number of characters with the same letter position and frequency is odd or even.

If any character satisfies any of the following conditions, then the character has the same frequency and letter position parity.

• If the character frequency in the string is an odd number, and the letter position is also an odd number.

• If the character frequency in the string is an even number, and the letter position is also an even number.

Example

enter

alpha = "dbbabcdc"

Output

Even

illustrate

• a has a frequency of 1 and a position of 1, so the parity is the same and the count becomes 1.

• d has a frequency of 2 and a position of 4. Therefore, since the parity bits are the same, the count becomes 2.

The count value is 2, which is an even number.

enter

alpha = "ppqqr"

Output

Odd

Explanation – Only the parity of ‘p’ is the same. Therefore, the count is 1 and the answer is an odd number.

enter

alpha = "pqqqqrrr";

Output

Even

Description - Parity is not the same for any character. So since the count value is zero, it prints "Even".

method 1

In this approach, we will use a map data structure to store the frequency of each string character. After that, we count the number of characters with the same parity in letter position and frequency.

algorithm

Step 1 - Define a count[] array of length 27 and initialize it with 0. Additionally, initialize "parity" with 0.

Step 2 - Store character frequencies in count[] array.

Step 3 - Make 26 iterations to go through each lowercase alphabetic character.

Step 4 - If count[p] is greater than 0, check if the character frequency and position have the same parity. If so, increase the Parity value by 1.

Step 5 - Finally, if the parity is divisible by 2, return "Even". Otherwise, return "odd".

Example

#include <bits/stdc++.h>
using namespace std;

string getParity(string alpha) {
    // To store the count of characters
    int count[27] = {0};
    int parity = 0;
    // Count frequency of each character
    for (int p = 0; p < alpha.size(); p++) {
        count[alpha[p] - 'a' + 1]++;
    }
    for (int p = 1; p <= 26; p++) {
        if (count[p] != 0) {
            // Increment parity for valid odd and even parity
            if (p % 2 == 0 && count[p] % 2 == 0 || p % 2 == 1 && count[p] % 2 == 1)
                parity++;
        }
    }
    // Return value based on final parity count
    if (parity % 2 == 1)
        return "ODD";
    else
        return "EVEN";
}
int main() {
    string alpha = "dbbabcdc";
    cout << "The parity of given string's character's is " << getParity(alpha);
    return 0;
}

Output

The parity of given string's character's is EVEN

Time complexity - O(N) for calculating the frequency of characters.

Space complexity - O(26) ~ O(1) to store the frequency of alphabetic characters.

Method 2

In this method, we will sort the given string. After that, whenever we get different adjacent characters, we check the frequency and position parity of the previous character.

algorithm

Step 1 - Initialize "Parity" to 0.

Step 2 - The sort() method is used to sort the given string.

Step 3 - Start traversing the string and initialize 'charCnt' to 0 to store the frequency of the current character.

Step 4 - If the current character is different from the next character, check if the parity and character position of "charCnt" match. If so, increase Parity by 1.

Step 5 - If the current character is the same as the previous character, increase "charCnt" by 1.

Step 6 - Finally, if the "parity" value is even, return "Even". Otherwise, return "odd".

Example

#include <bits/stdc++.h>
using namespace std;

string getParity(string alpha) {
    int parity = 0;
    // Sort the string
    sort(alpha.begin(), alpha.end());
    // Traverse the string
    for (int p = 0; p < alpha.size(); p++) {
        int charCnt = 0;        
        // When we get different adjacent characters
        if (alpha[p] != alpha[p + 1]) {
            // Validating the odd and even parties
            if (charCnt % 2 == 1 && (alpha[p] - 'a' + 1) % 2 == 1 || charCnt % 2 == 0 && (alpha[p] - 'a' + 1) % 2 == 0)
                parity++;
        } else {
            charCnt++;
        }
    }
    if (parity % 2 == 1)
        return "ODD";
    else
        return "EVEN";
}
int main() {
    string alpha = "abbbccdd";
    cout << "The parity of given string's character's is " << getParity(alpha);
    return 0;
}

Output

The parity of given string's character's is EVEN

Time complexity - O(NlogN) for sorting strings.

Space complexity - O(N) to sort strings.

The first method uses constant space, while the second method uses dynamic space to sort the given string. In addition, the second method has a higher time cost, so it is recommended to use the first method for better performance.

The above is the detailed content of Parity in the number of letters with the same letter position and frequency parity. For more information, please follow other related articles on the PHP Chinese website!