Road to Google – Part 7: Almost a Palindrome

Question:

Given a string, determine if it is almost a palindrome. A string is almost a palindrome if it becomes a palindrome by removing 1 letter. Consider only alphanumeric characters and ignore case sensitivity.

What is the question asking for?

Well, this time it’s quite straightforward, isn’t it? We’re given almost a palindrome, and if we delete one letter in it, it becomes a palindrome.

Let’s take a look at the first example that we saw in the previous post. “racecar” can be a palindrome by deleting either ‘e’ or ‘a’.

On the other hand, in the case of “zxccxxz”, if we delete an ‘x’, it becomes a palindrome. But if we delete a ‘c’, it’s not. So we have to be careful not to delete the wrong one.

Coding solution:

So, here’s the coding solution.

import java.util.Scanner;

class AlmostPalindrome {
    public static boolean isAlmostPalindrome(String input) {
        String clean = input.replaceAll("[^a-zA-Z0-9]", "").toLowerCase();
        int left = 0;
        int right = clean.length() - 1;
        int count = 0;

        while (left < right) {
            if (clean.charAt(left) != clean.charAt(right)) {
                count++;
                if (count > 1) {
                    return false;
                }
                if (clean.length() % 2 == 0) {
                    left++;
                } else {
                    right--;
                }
            } else {
                left++;
                right--;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        System.out.println("Enter a string: ");
        String input = scan.nextLine();

        if (isAlmostPalindrome(input)) {
            System.out.println("The string is almost a palindrome.");
        } else {
            System.out.println("The string is not almost a palindrome.");
        }
    }
}

Step-by-step description:

Inside the isAlmostPalindrome method, use the replaceAll method to remove all non-alphanumeric characters and convert the string to lowercase. Store the result in a String variable named clean.

String clean = input.replaceAll("[^a-zA-Z0-9]", "").toLowerCase();

Declare two variables named left and right to keep track of the indices while traversing the string. left is initialized to 0 and right is initialized to clean.length() – 1.

Declare a variable named count to keep track of the number of mismatches. Initialize it to 0.

int left = 0;
int right = clean.length() - 1;
int count = 0;

Use a while loop to traverse the string. The loop continues until left is no longer less than right.

In the loop, check if the characters at indices left and right are not equal.

If the characters are not equal, increment count by 1.

Check if count is greater than 1. If it is, return false because we can only remove one character.

If the string length is even, increment left by 1. If the string length is odd, decrement right by 1. This is because we only want to remove one character.

If the characters are equal, increment left by 1 and decrement right by 1.

After the loop, return true if count is less than or equal to 1.

while (left < right) {
            if (clean.charAt(left) != clean.charAt(right)) {
                count++;
                if (count > 1) {
                    return false;
                }
                if (clean.length() % 2 == 0) {
                    left++;
                } else {
                    right--;
                }
            } else {
                left++;
                right--;
            }
        }
        return true;
    }

In the main method, create a Scanner object named scan to read the input from the user.

Use the nextLine method to read a string from the user and store it in a String variable named input.

Call the isAlmostPalindrome method and pass input as an argument. Store the result in a boolean variable.

Use an if statement to print whether the string is almost a palindrome or not. If the result is true, print “The string is almost a palindrome.” If the result is false, print “The string is not almost a palindrome.”