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

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

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

问题陈述 - 我们给出了一个仅包含小写英文字母字符的字符串 alpha。我们需要检查字母位置和频率相同的字符数量是奇数还是偶数。

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

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

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

示例

输入

alpha = "dbbabcdc"

输出

Even

说明 

• a的出现频率为1，位置也为1，因此奇偶校验相同，计数变为1。

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

计数值为 2，为偶数。

输入

alpha = "ppqqr"

输出

Odd

说明 – 只有‘p’的奇偶校验相同。因此，计数为 1，答案为奇数。

输入

alpha = "pqqqqrrr";

输出

Even

说明 - 任何字符的奇偶校验都不相同。因此，由于计数值为零，它会打印“Even”。

红墨

一站式小红书图文生成器

下载

方法 1

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

算法

第 1 步 - 定义长度为 27 的 count[] 数组并用 0 初始化。此外，用 0 初始化“奇偶校验”。

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

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

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

第 5 步 - 最后，如果奇偶校验可被 2 整除，则返回“Even”。否则，返回“奇数”。

示例

#include 
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 步 - 将“奇偶校验”初始化为 0。

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

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

步骤 4 - 如果当前字符与下一个字符不同，请检查“charCnt”的奇偶校验和字符位置是否匹配。如果是，则将“奇偶校验”增加 1。

第 5 步 - 如果当前字符与前一个字符相同，则将“charCnt”增加 1。

第 6 步 - 最后，如果“奇偶校验”值为偶数，则返回“Even”。否则，返回“奇数”。

示例

#include 
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) 对字符串进行排序。

第一种方法采用常量空间，而第二种方法采用动态空间对给定字符串进行排序。另外，第二种方法的时间成本较高，因此建议使用第一种方法以获得更好的性能。