easy Palindrome Check using Queue

Problem Statement

Given a string s, determine if that string is a palindrome using a queue data structure. Return true if the string is a palindrome. Otherwise, return false.

A palindrome is a word, number, phrase, or other sequence of characters that reads the same forward and backward, ignoring spaces, punctuation, and capitalization.

Examples

Example 1

• Input: s = "madam"
• Output: true
• Explanation: The word "madam" reads the same forwards and backwards.

Example 2

• Input: s = "openai"
• Output: false
• Explanation: The word "openai" does not read the same forwards and backwards.

Example 3

• Input: s = "A man a plan a canal Panama"
• Output: true
• Explanation: The phrase "A man a plan a canal Panama" reads the same forwards and backwards when we ignore spaces and capitalization.

Solution

To solve this problem, the string is first preprocessed by removing all non-alphanumeric characters and converting it to lowercase to ensure consistency. Then, the characters of the cleaned string are stored in a deque (implemented as an array). The algorithm checks if the string is a palindrome by repeatedly removing and comparing characters from both the front and back of the deque. If all pairs of characters match as they are removed, the string is confirmed to be a palindrome; otherwise, it is not. This approach efficiently utilizes the deque's properties to verify the palindrome nature of the string.

Step-by-Step Algorithm

1. Normalize the String: Remove any spaces, punctuation, and convert all characters to the same case (lowercase or uppercase) to ensure consistency in comparison.

2. Initialize a Dequeue: Create an empty Dequeue that will be used to store characters of the string.

3. Enqueue Characters: Iterate over the normalized string and enqueue each character into the Dequeue.

4. Check for Palindrome:

   • Dequeue a character from the front and end of the queue.
   • Compare these two dequeued characters.
   • If at any point the two characters do not match, return false, indicating the string is not a palindrome.
   • Repeat step-4, until there are less than 2 characters left in the queue.

5. End of Queue: If you've iterated through the queue without finding a mismatch, return true, indicating the string is a palindrome.

Algorithm Walkthrough

Code

Here is how we can implement this algorithm:

import java.util.Deque;
import java.util.LinkedList;

public class Solution {

  public boolean checkPalindrome(String s) {
    // Remove all non-alphanumeric characters and convert to lowercase
    s = s.replaceAll("[^a-zA-Z0-9]", "").toLowerCase();
    // Create a deque (double-ended queue) from the string
    Deque<Character> deque = new LinkedList<>();
    for (char c : s.toCharArray()) {
      deque.addLast(c);
    }

    // Continue until there is 0 or 1 character left
    while (deque.size() > 1) {
      // Remove and compare characters from both ends
      if (!deque.pollFirst().equals(deque.pollLast())) {
        return false;
      }
    }
    return true;
  }

  public static void main(String[] args) {
    Solution sol = new Solution();
    System.out.println(sol.checkPalindrome("madam")); // returns: True
    System.out.println(sol.checkPalindrome("openai")); // returns: False
    System.out.println(sol.checkPalindrome("A man a plan a canal Panama")); // returns: True
  }
}

Complexity Analysis

Time Complexity

• Preprocessing (removing non-alphanumeric characters and converting to lowercase): The algorithm processes the input string once to remove non-alphanumeric characters and convert it to lowercase. This takes time, where N is the length of the input string.

• Deque operations:

  • Deque insertion: Each character from the preprocessed string is added to the deque in constant time, . This results in a total of for adding all characters to the deque.
  • Deque comparison: In the main loop, the algorithm compares characters from both ends of the deque. For each comparison, two characters are removed from the deque. This loop runs approximately times, resulting in operations.

Overall time complexity: , where N is the length of the input string.

Space Complexity

• Deque space: The deque stores all characters from the preprocessed string, requiring space.

• Additional space: The string that results from preprocessing (removing non-alphanumeric characters and converting to lowercase) also requires space.

Overall space complexity: .