字母位置和频率奇偶性相同的字母数量的奇偶性

---

在这个问题中，我们将计算频率和位置具有相同奇偶性的字符的数量，并将字符数量的奇偶性打印出来。

为了解决这个问题，我们可以找到字符串中每个字符的频率，并计算频率和位置具有相同奇偶性的字符总数。之后，我们可以根据计数打印奇数或偶数答案。

问题陈述 - 我们给定一个字符串 alpha，其中只包含小写英文字母。我们需要检查具有其字母位置和频率相同奇偶性的字符数量是奇数还是偶数。

如果字符满足以下任何条件，则任何字符具有相同的频率和字母位置奇偶性。

• 如果字符串中字符的频率为奇数，并且字母位置也为奇数。

• 如果字符串中字符的频率为偶数，并且字母位置也为偶数。

示例

输入

alpha = "dbbabcdc"

输出

Even

解释 

• ‘a’ 的频率为 1，位置也为 1。因此，两者具有相同的奇偶性，计数变为 1。

• ‘d’ 的频率为 2，位置为 4。因此，由于奇偶性位相同，计数变为 2。

计数的值为 2，它是偶数。

输入

alpha = "ppqqr"

输出

Odd

解释 – 只有 ‘p’ 的奇偶性相同。因此，计数为 1，答案为奇数。

输入

alpha = "pqqqqrrr";

输出

Even

解释 – 任何字符的奇偶性都不相同。因此，由于计数值为零，它打印 ‘偶数’。

方法 1

在这种方法中，我们将使用 map 数据结构来存储每个字符串字符的频率。之后，我们将计算具有字母位置和频率相同奇偶性的字符的数量。

算法

步骤 1 - 定义长度为 27 的 count[] 数组并初始化为 0。此外，将 ‘parity’ 初始化为 0。

步骤 2 - 将字符频率存储在 count[] 数组中。

步骤 3 - 进行 26 次迭代以遍历每个小写字母字符。

步骤 4 - 如果 count[p] 大于 0，则检查字符频率和位置是否具有相同的奇偶性。如果是，则将 ‘parity’ 值增加 1。

步骤 5 - 最后，如果 parity 可被 2 整除，则返回 ‘偶数’。否则，返回 ‘奇数’。

示例

#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;
}

输出

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

时间复杂度 - O(N) 用于计算字符的频率。

空间复杂度 - O(26) ~ O(1) 用于存储字母字符的频率。

方法 2

在这种方法中，我们将对给定的字符串进行排序。之后，每当我们获得不同的相邻字符时，我们将检查前一个字符的频率和位置的奇偶性。

算法

步骤 1 - 将 ‘parity’ 初始化为 0。

步骤 2 - sort() 方法用于对给定字符串进行排序。

步骤 3 - 开始遍历字符串，并将 ‘charCnt’ 初始化为 0 以存储当前字符的频率。

步骤 4 - 如果当前字符与下一个字符不同，则检查 ‘charCnt’ 的奇偶性与字符的位置是否匹配。如果是，则将 ‘parity’ 增加 1。

步骤 5 - 如果当前字符与前一个字符相同，则将 ‘charCnt’ 增加 1。

步骤 6 - 最后，如果 ‘parity’ 值为偶数，则返回 ‘偶数’。否则，返回 ‘奇数’。

示例

#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;
}

输出

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

时间复杂度 - O(NlogN) 用于对字符串进行排序。

空间复杂度 - O(N) 用于对字符串进行排序。

第一种方法占用恒定空间，而第二种方法占用动态空间对给定字符串进行排序。此外，第二种方法在时间上开销更大，因此建议使用第一种方法以获得更好的性能。