Category Archives: Palindrome

Character to be removed to become a palindrome

Given a string, We have to find out by removing which character, it becomes a palindrome.

For example consider the string “racercar”, the character ‘r’ at index 4 should be removed to become a palindrome.

The approach here is simple.

Start from both ends of the string and compare both characters. If they are equal, we increment the front index and decrement the back index. If they are not equal, one of the characters needs to be removed. We can check this by verifying if a palindrome can be formed by removing the front character or the back character. Repeat the above procedure until both indices meet each other.

We are printing the index of the character to be removed. If the string is already a palindrome, we print -1.

This solution has O(n) time complexity.

Here are the implementations in C++.

Generating next bigger palindrome of a number

Given a number, how do we generate a smallest number which is greater than the given number and is a palindrome?

Consider the following examples

Input    Output
3         4
9         11
13        22
767       777
594       595
898       909
999       1001

Here is the solution approach. This problem has multiple cases to be considered.

Case 1: 
If all the digits in the number are ‘9’, the output is simply 1 followed by (d-1) 0’s followed by 1, where d is the number of digits in the original number.

Example: 9999, d = 4, so the output is 10001

Case 2:
How do we get a palindrome from a given number with least number of changes?
If the given number itself is a palindrome, obviously we need not make any changes.
Otherwise there are two ways to do that. Replicate the right half with left or replicate the left half with right.

Consider the number 230847, the two possibilities are 230032 and 748847
for 6195824, the two possibilities are 6195916 and 4285824.

Observe that if we replicate left half with right half, we are getting the numbers far from the given number. This is because as we move from right to left, the place value of the digit increases. But we want the number which is just greater than the given number with least difference.

So we have to replicate the right half with left half.

Are we done if we just replace the right half with left half? No.

Let us see the same example of 230847, if we replicate as said above, the result is 230032.
What is the problem with this number? It is a palindrome; but it is smaller than the given number. We wanted a number which is just greater.

So how to make this number just bigger?

Increment the middle digit(s) and propagate the carry if any towards the left and the right.

If the number has even number of digits, there will be two middle digits; otherwise it has just one middle digit.

230032 becomes 231132 and that is the required answer.

Let us consider one more example with carry propagation, 849948. After incrementing middle digits, it becomes 850058.

Here is the C++ implementation of the above algorithm.

Check if a number is the mirror image of itself

Given an arbitrarily large number, how to check if it is same as it’s mirror image.

For example 101 is a mirror image of itself, where as 1811 is not a mirror image of itself.

This problem is from Hacker earth (A website for competitive programming). If you want to solve this problem on your own, and execute it on different possible test cases for it’s correctness, follow this link. If you just want to know the solution, read on…

The solution is simple; the number should only contain the digits from the set {0,1,8} because they look the same when read in a mirror and it should also be a palindrome.

Here is the simple program to do this.

Checking if any anagram of a given string is palindrome or not

Given a string, how do we check if any anagram of it can be a palindrome?
For example let us consider the string “AAC”. An anagram of it is “ACA” which is a palindrome. We have to write a method which takes a string and outputs true if we can form a palindrome from any anagram of the given string. Otherwise outputs false.
We can immediately think of a solution where we can generate all anagrams of the given string and check if there is any palindrome exists. But this approach is very lengthy and has exponential time complexity (O(n!)).
The key to solve this problem efficiently is to understand how a palindrome is formed. We all know that a palindrome reads the same when you read from left to right or right to left. 

A palindrome can be broken into two halves. where in the first half is the reverse of second half. In case of odd length of strings, we have to ignore the middle character.

So for every character in the first half, there is a corresponding matching character in the second half. This indicates that all the characters in a string must occur even number of times except for one which appears in the middle of the string.

Hence if we check if there is at most one character with odd occurrences in the string we can say that we can form a palindrome from any anagram.

Here is the Java code which implements this algorithm. For simplicity, I assumed that the input string contains only lowercase English alphabets.