Manacher's Algorithm for Longest Palindromic Substring

Identifying the longest palindromic substring within a string requires handling both odd and even-length palindromes. A common approach involves expanding from each center, but this method fails to detect even-length palindromes. The solution is to insert a delimiter character between each character, converting the search space uniformly. However, a naive expansion strategy results in O(N²) worst-case performance, particularly with strings of identical characters.

Manacher's algorithm reduces this to linear O(N) time. It maintains a center C and the rightmost boundary R of the palindrome found so far. For each position i:

1. If i is outside R, perform brute-force expansion.
2. If i is within R, use the precomputed radius of its mirror position i_mirror around C to initialize the radius at i. The subsequent logic has three cases based on i_mirror's palindrome boundaries relative to the left boundary L: a. If i_mirror's palindrome is entirely within L..R, radius[i] = radius[i_mirror]. b. If i_mirror's palindrome extends beyond L, radius[i] = R - i. c. If i_mirror's palindroem touches L, radius[i] is at least radius[i_mirror] and may expand further.
3. Update C and R if a larger right boundary is found. The maximum radius minus one yields the original string's palindrome length.

public class LongestPalindromeFinder {
    private char[] insertDelimiters(char[] original) {
        char[] transformed = new char[original.length * 2 + 1];
        int srcIdx = 0;
        for (int i = 0; i < transformed.length; i++) {
            transformed[i] = (i % 2 == 0) ? '|' : original[srcIdx++];
        }
        return transformed;
    }

    public int computeLongestPalindromeLength(char[] input) {
        if (input == null || input.length == 0) return 0;
        char[] transformed = insertDelimiters(input);
        int[] palindromeRadii = new int[transformed.length];
        int maxRadius = Integer.MIN_VALUE;
        int center = -1, rightBoundary = -1;

        for (int idx = 0; idx < transformed.length; idx++) {
            // Determine initial expansion radius
            palindromeRadii[idx] = (rightBoundary > idx) ?
                Math.min(palindromeRadii[2 * center - idx], rightBoundary - idx) : 1;

            // Attempt to expand
            while (idx + palindromeRadii[idx] < transformed.length &&
                   idx - palindromeRadii[idx] >= 0) {
                if (transformed[idx + palindromeRadii[idx]] == transformed[idx - palindromeRadii[idx]]) {
                    palindromeRadii[idx]++;
                } else {
                    break;
                }
            }

            // Update center and boundary if a larger palindrome is found
            if (idx + palindromeRadii[idx] > rightBoundary) {
                rightBoundary = idx + palindromeRadii[idx];
                center = idx;
            }
            maxRadius = Math.max(maxRadius, palindromeRadii[idx]);
        }
        return maxRadius - 1;
    }
}

Sliding Window Maximum with Deque

For a given array and a window of fixed size, the goal is to efficiently determine the maximum element within each sliding window. A double-ended queue (deque) maintains candidate indices in descending order of their corresponding values. The front of the deque always holds the index of the current window's maximum.

• When the right pointer moves to include a new element, indices are popped from the back of the deque while their values are less than or equal to the new element. The new index is then added to the back.
• When the left pointer moves to exclude an element, if the index being removed is at the front of the deque, it is popped.
• Each element enters and exits the deque exactly once, yielding an amortized O(1) cost per operation and O(N) overall.

import java.util.LinkedList;

public class SlidingWindowMaximum {
    public int[] findMaxForEachWindow(int[] data, int windowSize) {
        if (data == null || windowSize < 1 || data.length < windowSize) {
            return null;
        }
        LinkedList<Integer> indexDeque = new LinkedList<>();
        int[] result = new int[data.length - windowSize + 1];
        int resultIdx = 0;

        for (int currentIdx = 0; currentIdx < data.length; currentIdx++) {
            // Remove indices from the back whose values are <= current value
            while (!indexDeque.isEmpty() && data[indexDeque.peekLast()] <= data[currentIdx]) {
                indexDeque.pollLast();
            }
            indexDeque.addLast(currentIdx);

            // Remove the front index if it's outside the current window
            if (indexDeque.peekFirst() == currentIdx - windowSize) {
                indexDeque.pollFirst();
            }

            // Record the maximum once the window is fully formed
            if (currentIdx >= windowSize - 1) {
                result[resultIdx++] = data[indexDeque.peekFirst()];
            }
        }
        return result;
    }
}

Monotonic Stack for Nearest Greater Elements

To find the nearest greater element to the left and right for each position in an array, a monotonic stack can be used. For finding greater elements, maintain a stack where indices are stored in descending order of their values from bottom to top.

• Iterate through the array. For each element, while the stack is not empty and the current value is greater than the value at the index on the stack's top, pop the top. For the popped index, its right greater element is the current value; its left greater element is the value at the new top of the stack (if any).
• Push the current index onto the stack.
• After processing all elements, pop remaining indices. They have no right greater element; their left greater element is the value at the next index in the stack.
• For arrays with duplicate values, store lists of indices in the stack. The logic remains similar, with the entire list processed up on popping. This process ensures each index is pushed and popped once, resulting in O(N) time.

import java.util.Stack;
import java.util.ArrayList;

public class NearestGreaterNeighbors {
    public void printNearestGreater(int[] values) {
        if (values == null || values.length == 0) return;
        Stack<Integer> indexStack = new Stack<>();

        for (int i = 0; i < values.length; i++) {
            while (!indexStack.isEmpty() && values[indexStack.peek()] < values[i]) {
                int poppedIdx = indexStack.pop();
                String leftGreater = indexStack.isEmpty() ? "None" : String.valueOf(values[indexStack.peek()]);
                System.out.println("Index: " + poppedIdx + ", Value: " + values[poppedIdx] +
                                   ", Left Greater: " + leftGreater + ", Right Greater: " + values[i]);
            }
            indexStack.push(i);
        }

        while (!indexStack.isEmpty()) {
            int poppedIdx = indexStack.pop();
            String leftGreater = indexStack.isEmpty() ? "None" : String.valueOf(values[indexStack.peek()]);
            System.out.println("Index: " + poppedIdx + ", Value: " + values[poppedIdx] +
                               ", Left Greater: " + leftGreater + ", Right Greater: None");
        }
    }
}