O(N) Manacher's Algorithm with Mirror Boundary Optimization

Dipaditya Das — Wed, 15 Jul 2026 18:36:13 +0000

Intuition

Manacher's Algorithm leverages the symmetry of palindromes to avoid redundant comparisons. Instead of treating odd- and even-length palindromes separately, the input string is transformed by inserting a special character (#) between every character and adding sentinel characters (^ and $) at both ends. This allows every palindrome to be treated as an odd-length palindrome.

While traversing the transformed string, the algorithm maintains the center and right boundary of the rightmost palindrome found so far. For each position, it uses the palindrome information from its mirror position (with respect to the current center) to initialize the palindrome radius, significantly reducing unnecessary expansions. Only when the palindrome reaches beyond the current right boundary is additional expansion performed.

This optimization ensures that every character is expanded at most a constant number of times, resulting in linear time complexity.

Approach

Handle the edge case by returning an empty string if the input string is empty.
Transform the input string by inserting # between every character and adding sentinel characters (^ and $) at both ends to treat odd- and even-length palindromes uniformly.
Create a palindrome radius array p, where p[i] stores the radius of the palindrome centered at index i in the transformed string.
Initialize the variables center and right to represent the center and right boundary of the current rightmost palindrome.
Initialize max_len and center_index to keep track of the longest palindrome found during traversal.
Traverse the transformed string from left to right, ignoring the sentinel characters.
Compute the mirror index of the current position using the current palindrome's center.
If the current index lies within the current right boundary, initialize its palindrome radius using the previously computed mirror information.
Expand around the current center while the characters on both sides are equal, increasing the palindrome radius accordingly.
If the expanded palindrome extends beyond the current right boundary, update the center and right variables.
If the current palindrome is longer than the previously recorded longest palindrome, update max_len and center_index.
Convert the center position from the transformed string back to the corresponding starting index in the original string.
Return the longest palindromic substring using the calculated starting index and maximum length.

Complexity

Time complexity: O(n)
Each character in the transformed string is expanded at most once beyond the current right boundary. Thanks to the mirror optimization, redundant comparisons are eliminated, giving an overall linear runtime.
Space complexity: O(n)
Additional space is used for the transformed string and the palindrome radius array (p).

Code

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if not s:
            return ""

        # Transform the string to handle even and odd palindromes uniformly.
        # Example:
        # "abba" -> "^#a#b#b#a#$"
        t = "^#" + "#".join(s) + "#$"
        n = len(t)

        # p[i] = radius of palindrome centered at i
        p = [0] * n

        center = 0
        right = 0

        max_len = 0
        center_index = 0

        for i in range(1, n - 1):

            mirror = 2 * center - i

            # Use previously computed palindrome information
            if i < right:
                p[i] = min(right - i, p[mirror])

            # Expand around center i
            while t[i + p[i] + 1] == t[i - p[i] - 1]:
                p[i] += 1

            # Update center and right boundary
            if i + p[i] > right:
                center = i
                right = i + p[i]

            # Track the longest palindrome
            if p[i] > max_len:
                max_len = p[i]
                center_index = i

        # Convert index in transformed string back to original string
        start = (center_index - max_len) // 2

        return s[start:start + max_len]

ZSH + Starship: A Better Shell Experience for Linux Power Users

Dipaditya Das — Thu, 16 Apr 2026 17:58:26 +0000

🚀 A Production-Ready Shell Lifecycle Manager with Starship Integration

🔗 GitHub Repository

👉 https://github.com/DipadityaDas/InstallZsh.git

🐚 What is ZSH (and Why Use It?)

ZSH (Z Shell) is an advanced Unix shell designed to be a more powerful and user-friendly alternative to Bash.

It provides:

Smarter tab completion
Command auto-suggestions
Better globbing and scripting capabilities
Plugin ecosystem (via frameworks or standalone plugins)
Improved developer ergonomics

For power users and engineers, ZSH significantly enhances productivity compared to traditional shells.

⚡ What is Starship?

Starship is a fast, minimal, and highly customizable cross-shell prompt.

Instead of heavy frameworks, Starship delivers:

Blazing-fast prompt rendering (written in Rust)
Git-aware status indicators
Language/runtime detection (Node, Python, etc.)
Clean and consistent prompt across shells

It integrates seamlessly with ZSH and replaces traditional prompt customization approaches.

🔍 Why This Project Exists

In real-world environments (especially shared systems, lab setups, or enterprise fleets), manually configuring ZSH per user introduces:

Configuration drift
Broken environments
No rollback strategy
Inconsistent developer experience

This tool solves those problems with a state-driven and reversible approach.

📦 Key Features

✅ Per-user installation and rollback
✅ Deterministic state tracking
✅ Safe .zshrc deployment (non-destructive)
✅ Starship prompt integration
✅ Plugin management:
- autosuggestions
- syntax highlighting
✅ Full cleanup mode
✅ Centralized logging

⚙️ Supported Systems

Fedora
RHEL
AlmaLinux
Rocky Linux

🚀 Quick Start

1. Download the Script

git clone https://github.com/DipadityaDas/InstallZsh.git
cd InstallZsh
chmod +x zsh_manager.sh

2. Install ZSH for a User

sudo ./zsh_manager.sh install <username>

Example:

sudo ./zsh_manager.sh install dipaditya

🔧 What the Script Does

Behind the scenes, the script:

Saves the current shell state
Installs dependencies:
- zsh, git, fzf, curl
Enables Starship via COPR
Installs plugins:
- zsh-autosuggestions
- zsh-syntax-highlighting
Deploys configs:
- /etc/starship/starship.toml
- ~/.zshrc
Switches the user shell to ZSH

🔍 Check Status

sudo ./zsh_manager.sh status <username>

🔄 Revert Anytime (Safely)

Standard Revert

sudo ./zsh_manager.sh revert <username>

Full Cleanup Mode

sudo ./zsh_manager.sh revert <username> --full-cleanup

📂 File Structure

Path	Purpose
`/var/lib/zsh_manager/`	State tracking
`/var/log/zsh_manager.log`	Logs
`/etc/starship/starship.toml`	Global config
`~/.zshrc`	User config

🛡️ Safety First

State-based rollback (no guesswork)
Existing .zshrc is preserved
System users are skipped
Designed for idempotent execution

🧪 Example Workflow

sudo ./zsh_manager.sh install dipaditya
sudo ./zsh_manager.sh status dipaditya
sudo ./zsh_manager.sh revert dipaditya
sudo ./zsh_manager.sh revert dipaditya --full-cleanup

💡 Future Enhancements

Dry-run mode (--dry-run)
Bulk user operations (--all-users)
RPM packaging
Ansible role integration
Version flag support

📜 License

MIT License

👨‍💻 Author

Dipaditya Das

If you’re managing multiple Linux users and want a clean, reversible, and automated ZSH setup with a modern Starship prompt, this approach will significantly reduce manual effort and eliminate configuration drift.

Feedback, issues, and contributions are welcome on GitHub.

DEV Community: Dipaditya Das