Introduction
Before discussing the problem of ‘break a palindrome’, we first need to know about palindromes. A palindrome is a string that reads the same backward as forwards. It means if we reverse the string, then reversed string and the original string will be the same. For example, ‘madam’, ‘aaabaaa’, etc.
Problem Statement (break a palindrome)
Suppose you are given a string str. The given string str contains all the lowercase English alphabet characters. Also, the given string is palindromic. You need to replace exactly one character with any lowercase English alphabet. After replacing exactly one character, the resulting string is not a palindrome, and that should be lexicographically the smallest possible string after replacing exactly one character.
Suppose there is no way to make it not a palindrome after replacing exactly one character, then return an empty string.
Lexicographically Smaller: A string x is lexicographically smaller than a string y (of the same length) if x has a character strictly smaller than the equivalent character in y in the first position where x and y differ. For example, "adde" is lexicographically smaller than "aedc" because they differ at the 2nd and 4th characters but it is lexicographically smaller because they first differ at the 2nd character, and 'd' is smaller than 'e'.
Example
Input: str = "aabccbaa"
Output: "aaaccbaa"
Explanation: There are many ways to make aabccbaa, not a palindrome. “babccbaa”, “aabccdaa”, and “aaaccbaa” are some of the ways to make it not a palindrome. But the lexicographically smallest way is to replace the third character with ‘a’, so the string becomes “aaaccbaa”.
Approach
We can solve this problem using two pointer approach. The general approach is to traverse from the left as well as the right at the same time. Let's say ‘n’ is the length of the string, ‘l’ is the left pointer, and ‘r’ is the right pointer. While iterating through the string, if string[l] is equal to ‘a’, then increase the value of l by 1 and decrease the value of r by 1. If at any value of l string[l] is not equal to ‘a’, replace that character with ‘a’ and return the string.
But we have two edge cases they are as follows:
- The thing to notice is that if the length of the string is one, then we need to return an empty string.
- If the whole string consists of the ‘a’ letter, then change the last character of the string to ‘b’.
Let us move towards the implementation of the above approach.
Complexity
Time Complexity: The time complexity of the above approach for the ‘break a palindrome’ problem will be O(n). Here n is the size of the palindromic string as we are iterating the string only once, so the time complexity is O(n).
Space Complexity: Other than the string, we need O(1) space to solve the ‘break a palindrome’ problem.
Code
C++
Below is the implementation of the ‘break a palindrome’ problem. The following code is written in C++.
#include<bits/stdc++.h>
using namespace std;
string breakThePalindrome(string str) {
/* Length of the string */
int n = str.size();
/* Check if the length of the string is 1 */
if(n == 1){
return "";
}
/* Two pointer left and right */
int l = 0, r = n-1;
while(l < r){
/* If the character is 'a' increase l and decrease r */
if(str[l] == 'a'){
l++; r--;
}else{
/* If the character is not 'a' then replace it with 'a' and return the string */
str[l] = 'a';
return str;
}
}
/* If all the characters are 'a' replace the last character with 'b' */
str[n-1] = 'b';
return str;
}
int main(){
string str;
cout<<"Enter the string: ";
cin>>str;
cout<<breakThePalindrome(str);
return 0;
}
Output
Input:
"aabccbaa"Output:
"aaaccbaa"
Python
Below is the implementation of the ‘break a palindrome’ problem written in Python.
def breakThePalindrome(str):
"""Length of the string"""
n = len(str)
"""Check if the length of the string is 1"""
if n == 1:
return ""
"""Two pointer left and right"""
l = 0
r = n-1
while l < r:
"""If the character is 'a' increase l and decrease r"""
if str[l] == 'a':
l+=1
r-=1
else:
"""If the character is not 'a' then replace it with 'a' and return the string"""
# str[l] = 'a'
return str[:l] + "a" + str[l + 1:]
"""If all the characters are 'a' replace the last character with b"""
return str[:n-1] + "b"
str = input("Enter the string: ")
print(breakThePalindrome(str))
Output
Input:
"aabccbaa"Output:
"aaaccbaa"
Java
Below is the implementation of the ‘break a palindrome’ problem written in Java.
import java.util.*;
class Problem{
public static String breakThePalindrome(String str) {
/* Length of the string */
int n = str.length();
/* Check if the length of the string is 1 */
if(n == 1){
return "";
}
/* Two pointer left and right */
int l = 0, r = n-1;
while(l < r){
/* If the character is 'a' increase l and decrease r */
if(str.charAt(l) == 'a'){
l++; r--;
}else{
/* If the character is not 'a' then replace it with 'a' and return the string */
return str.substring(0, l) + 'a' + str.substring(l + 1);
}
}
/* If all the characters are 'a' replace the last character with 'b' */
return str.substring(0, n-1) + 'b';
}
/* Main driver */
public static void main(String[] args){
Scanner sc= new Scanner(System.in);
System.out.print("Enter a string: ");
String str= sc.nextLine();
System.out.print(breakThePalindrome(str));
sc.close();
}
}
Output
Input:
str = "c"Output:
""
Explanation: The output will be an empty string because a single character is always said to be a palindrome. So, we will just return an empty string.
Try and compile by yourself with the help of online C++ Compiler for better understanding.
Check out this problem - Check If A String Is Palindrome
You can also read about Palindrome Number in Python here.
117+ registered 