UVA - 11475 - Extend to Palindrome

This article will explain my thought process to solve a problem called Extend to Palindrome (PDF) from UVA Online Judge. Read the original problem statement before reading this article.

Keywords: Palindrome, Two Pointers, Brute Force

Objective

Given:

A text.

We want to:

Find the smallest possible palindrome.

Glossary

Palindrome — A palindrome is a word, number, phrase, or other sequence of symbols that reads the same backwards as forwards.
Two Pointers — A technique of using two variables that move through the data structure in a coordinated way.
Brute Force — A search strategy that systematically explores every option until the answer is discovered.

Observation

We can use two pointers technique to validate whether a string is a palindrome. Both pointers scanning the string in an opposite direction to ensure backwards and forwards equality.

Since we want to produce the smallest possible palindrome by appending letters at the end of the text, we could brute force every possible length of palindrome, from length until 2 * length, until the smallest palindrome is found.

Algorithm

The two pointers can be implemented by using the first pointer as the start of the palindrome string and the second pointer as the end of the palindrome string. We keep incrementing the first pointer and decrementing the second pointer until they meet in the middle. In each iteration, check whether both pointers have the same letters.

During the brute force, to construct the palindrome string, we split the text into 2 pieces: (1) non-palindrome prefix, (2) palindrome suffix. If (2) is a valid palindrome, we can reverse and append (1) into the end of the text to form a valid palindrome.

The time complexity of this solution is O({length}^2) or O(10^10).

Implementation

import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * 11475 - Extend to Palindrome
 * Time limit: 3.000 seconds
 * https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2470
 */
public class Main {
    public static void main(final String... args) {
        final Scanner in = new Scanner(new BufferedInputStream(System.in));
        final PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
        final Process process = new Process();

        while (in.hasNext()) {
            final Input input = new Input();
            input.text = in.next();
            final Output output = process.process(input);
            out.println(output.palindrome);
        }

        in.close();
        out.flush();
        out.close();
    }
}

class Input {
    public String text;
}

class Output {
    public String palindrome;
}

class Process {
    public Output process(final Input input) {
        final Output output = new Output();

        final String text = input.text;
        final int textLength = text.length();
        for (int palindromeLength = textLength; palindromeLength <= 2 * textLength; palindromeLength++) {
            final boolean isPalindrome = isPalindrome(text, textLength, palindromeLength);
            if (isPalindrome) {
                final String palindrome = buildPalindrome(text, textLength, palindromeLength);
                output.palindrome = palindrome;
                break;
            }
        }

        return output;
    }

    private boolean isPalindrome(final String text, final int textLength, final int palindromeLength) {
        final int skipLength = palindromeLength - textLength;
        for (int left = skipLength, right = textLength - 1; left < right; left++, right--) {
            final boolean isEquals = text.charAt(left) == text.charAt(right);
            if (!isEquals) return false;
        }
        return true;
    }

    private String buildPalindrome(final String text, final int textLength, final int palindromeLength) {
        final int skipLength = palindromeLength - textLength;

        final StringBuilder palindrome = new StringBuilder(palindromeLength);
        for (int i = 0; i < skipLength; i++) palindrome.append(text.charAt(i));
        for (int i = skipLength; i < textLength; i++) palindrome.append(text.charAt(i));
        for (int i = skipLength - 1; i >= 0; i--) palindrome.append(text.charAt(i));

        return palindrome.toString();
    }
}