Checks whether all characters in a string can be made equal by increasing or decreasing

In this problem, we need to check whether all the characters of the string can be made equal by increasing and decreasing operations. We can get the weight of each character based on its ASCII value and check if the total weight can be used to make all characters equal.

Problem Statement – We are given a string str of length N containing lowercase alphabetic characters. We need to check if we can make all the characters in the string equal by selecting either of the two characters, increasing one character, and then decrementing the other character by 1. Prints "yes" if possible, otherwise prints "no".

ExampleExample

Input– str = ‘aedb

Output-str = ‘aedb

Explanation - ‘a’ can be increased by 2 and ‘e’ can be decreased by 2. At the same time, 'b' can be incremented by 1 and 'd' can be incremented by 1. Therefore, the resulting string can be 'cccc'.

Input– str = ‘abd’

Output-"No"

Explanation – We cannot make all characters of a string equal by increasing and decreasing operations

Enter-‘g’

Output - 'Yes'

Explanation – A string contains only a single character, so all string characters are already equal

method one

In this method, we will calculate the total character weight of the string. The weights of characters are defined as ‘a’ = 1, ‘b’ = 2, ‘c’ = 3, …, ‘z’ = 26. So if we divide the total weight by the length of the string, we can say that by increasing one character and decreasing another, we make all characters of the string equal.

algorithm

• Define the "len" variable and use the size() method to store the size of the string.

• Define the "totalWeight" variable to store the total weight of all characters of a given string

• Get the weight of a specific character using the ASCII code of each character and add it to the "totalWeight" variable.

• Returns true if the value of "totalWeight" is divisible by "len". Otherwise, returns false.

Example

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

Output

Yes

Time complexity - O(N), since we iterate over the string.

Space complexity - O(1), because we use constant space.

in conclusion

We learned to check whether all characters of a string can be equal by increasing and decreasing the ASCII value of the character. We solve this problem in terms of "total weight". The user can also try to find the resulting string. To find the resulting string, find the ASCII value corresponding to (totalWeight/len) and add "len" characters to the given string.

The above is the detailed content of Checks whether all characters in a string can be made equal by increasing or decreasing. For more information, please follow other related articles on the PHP Chinese website!