检查字符串的所有字符是否可以通过增量或减量操作使其相等

在这个问题中，我们需要检查是否可以通过增量和减量操作使字符串的所有字符相等。我们可以根据每个字符的 ASCII 值获得每个字符的权重，并检查总权重是否可以用于使所有字符相等。

问题陈述 – 我们给定一个长度为 N 的字符串 str，其中包含小写字母字符。我们需要检查是否可以通过选择任意两个字符，一个增加 1，另一个减少 1，来使字符串的所有字符相等。如果可能，打印“yes”，否则打印“no”。

示例

输入– str = ‘aedb

输出 – str = ‘aedb

说明 – ‘a’ 可以增加 2，而 ‘e’ 可以减少 2。同样，‘b’ 可以增加 1，而 ‘d’ 可以增加 1。因此，结果字符串可以是 ‘cccc’。

输入– str = ‘abd’

输出 – ‘否’

说明 – 我们无法通过增量和减量操作使字符串的所有字符相等

输入– ‘g’

输出 – ‘是’

说明 – 字符串仅包含单个字符，因此所有字符串字符都已相等

方法 1

在这种方法中，我们将计算字符串字符的总权重。字符的权重定义为 ‘a’ = 1，‘b’ = 2，‘c’ = 3，…，‘z’ = 26。因此，如果我们将总权重除以字符串的长度，我们可以说我们可以通过增加一个字符并减少另一个字符来使字符串的所有字符相等。

算法

  • 定义 ‘len’ 变量并使用 size() 方法存储字符串的大小。

  • 定义 ‘totalWeight’ 变量以存储给定字符串所有字符的总权重

  • 使用每个字符的 ASCII 码获取特定字符的权重并将其添加到 ‘totalWeight’ 变量中。

  • 如果 ‘totalWeight’ 的值为 ‘len’ 的倍数，则返回 true。否则，返回 false。

示例

Open Compiler
#include <iostream>
using namespace std;

// function to check if all characters of a string can be made equal by incrementing or decrementing by 1
bool canMakeEqual(string str){
   int len = str.size();
   // store sum of ASCII values of characters
   int totalWeight = 0;
   // Iterate over the string
   for (int i = 0; i < len; i++){
      // get the ASCII value of each character
      totalWeight += str[i] - 'a' + 1;
   }
   return (totalWeight % len == 0);
}
int main(){
   string str = "aedb";
   if (canMakeEqual(str))
      cout << "Yes";
   else
      cout << "No";
   return 0;
}

输出

Yes

时间复杂度 – O(N)，因为我们遍历了字符串。

空间复杂度 – O(1)，因为我们使用了常数空间。

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

结论

我们学习了如何检查字符串的所有字符是否可以通过增量和减量字符的 ASCII 值来使其相等。我们根据“总权重”解决了这个问题。用户还可以尝试找到结果字符串。要找到结果字符串，请找到相对于 (totalWeight / len) 的 ASCII 值，并在给定字符串中添加 ‘len’ 个字符。

更新于: 2023年8月10日

155 次查看

开启你的 职业生涯

通过完成课程获得认证

开始
广告