Make a string non-palindrome by inserting the given characters

Problem Statement

We are given the string str and the character c in the input. We need to insert the given character c into the string at the index in order to convert the string into a non-palindrome. If we cannot convert the string to a non-palindrome, print "-1".

Example

enter

str = ‘nayan’, c = ‘n’

Output

‘nnayan’

The translation of

Explanation

is:

Explanation

There can be multiple output strings because we can insert "n" at any index of the given string. Therefore, the output string can be "nnayan", "nanyan", "naynan", "nayann", etc.

enter

str = ‘sss’, c = ‘s’

Output

‘-1’

The translation of

Explanation

is:

Explanation

No matter where we insert "s" in the given string, it is always a palindrome.

enter

str = ‘tutorialspoint’, c = ‘p’

Output

‘ptutorialspoint’

The translation of

Explanation

is:

Explanation

Since str is already a non-palindrome, it prints the same string by inserting the character c at the first index.

The logic to solve the above problem is that if all characters in a given string are equal to the given character c, it cannot make it a palindrome. Otherwise, add a character at the first position and check whether the resulting string is a palindrome. If so, insert the given character at the end.

method one

In this method, we use while loop to check if the given string is a palindrome and for loop to check if all the characters in the given string are the same.

algorithm

• Step 1 - Initialize the "cnt" variable to store the character count equal to the given character c.

• Step 2 - Use a for loop to iterate over the string. If the character at index i in the string is equal to character c, add 1 to the value of "cnt".

• Step 3 - If the value of 'cnt' is equal to the length of the string, print '-1' and execute the return statement.

• Step 4 − Initialize a 'temp' variable using c str. After that, use the isPalindrome() function to check if the given string is a palindrome.

• Step 5 - Define the isPalindrome() function.

• Step 5.1 - Define variable 'left' and initialize it to 0. Also, define the variable 'right' and initialize it to the length of the string minus 1.

• Step 5.2 - Use a while loop and match the characters at the beginning and end of the string. Additionally, increase the value of the "left" variable and decrease the value of the "right" variable.

• Step 5.3 - If any mismatch is found, return false; otherwise, return true when all loop iterations are completed.

• Step 6 - If the value of the "temp" variable is a non-palindrome, print it; otherwise, print str c.

The Chinese translation of

Example

is:

Example

#include <bits/stdc++.h>
using namespace std;
// Function to check if a string is a palindrome
bool isPalindrome(string str) {
   int left = 0;
   int right = str.length() - 1;
   // Keep comparing characters while they are the same
   while (right > left) {
      if (str[left++] != str[right--]) {
         return false;
      }
   }
   return true;
}
// Function to make a string non-palindrome by adding a character
void makeNonPalindrome(string str, char c) {
   int cnt = 0;
   for (int i = 0; i < str.length(); i++) {
      if (str[i] == c) {
         cnt++;
      }
   }
   if (cnt == str.length()) {
      cout << "-1";
      cout << "We can convert the string into a non-palindromic string by adding a given character at any position.";
      return;
   }
   cout << "Non-palindromic string is: " << endl;
   // append the character at the start, and check if it is a palindrome
   string temp = c + str;
   if (!isPalindrome(temp)){
      cout << temp << endl;
   } else {
      cout << str + c << endl;
   }
}
int main(){
   string str = "sass";
   char c = 's';
   makeNonPalindrome(str, c);
   return 0;
}

Output

Non-palindromic string is: 
sasss

• Time complexity - O(N) because we use a for loop to count the total number of characters equal to the given characters.

• Space Complexity - O(1) since we are not using any extra space.

Method 2

In this method, we use the same logic as in the first method, but we use a for loop to check if the string is a palindrome. Additionally, we have used the count() method to count the total number of given characters in the string.

algorithm

• Step 1 - Use count() method, passing string as first parameter and given character c as second parameter to count the number of characters equal to the given character in in the string.

• Step 2 - If the value returned by the count() method is equal to the length of the string, print "-1".

• Step 3 - In the isPalindrome() function, initialize 'i' to 0 and 'j' to the length of the string - 1. After that, the user uses a loop to iterate and compare the starting and ending characters. If any mismatch occurs, return false.

• Step 4 − Insert the given character at any position and check whether the string is non-palindrome. If the resulting string is a non-palindrome, we have the answer; otherwise, change the position of the given character in the string and check again.

The Chinese translation of

Example

is:

Example

#include <bits/stdc++.h>
using namespace std;
// Function to check if a string is a palindrome
bool isPalindrome(string str) {
   // Start from the leftmost and rightmost corners of str
   for (int i = 0, j = str.length() - 1; i < j; i++, j--){
      // If there is a mismatch, then the string is not palindrome; return false.
      if (str[i] != str[j])
         return false;
   }
   return true;
}
// Function to make a string non-palindrome by adding a character
void makeNonPalindrome(string str, char c){
   //   if all characters are the same as a given character, then the string cannot be made non-palindrome
   if (count(str.begin(), str.end(), c) == str.length()) {
      cout << "-1";
      cout << "We can convert the string into a non-palindromic string by adding a given character at any position.";
      return;
   }
   cout << "Non-palindromic string is: " << endl;
   // append the character at the start, and check if it is a palindrome
   string temp = c + str;
   if (!isPalindrome(temp)){
      cout << temp << endl;
   } else {
      cout << c + str << endl;
   }
}
int main() {
   string str = "nayan";
   char c = 'n';
   makeNonPalindrome(str, c);
   return 0;
}

Output

Non-palindromic string is: 
nnayan

• Time complexity - O(N)

• Space Complexity - O(1)

in conclusion

We learned two methods to convert a given string into a non-palindrome string, that is, insert the given character at any position. Both methods use the same logic but in first method we have written manual function to count the number of same characters which are equal to given character while in second method we have used count() method .

The first method is more suitable for learning purposes, and the second method is more suitable for real-time development.

The above is the detailed content of Make a string non-palindrome by inserting the given characters. For more information, please follow other related articles on the PHP Chinese website!