Grokking Data Structures & Algorithms for Coding Interviews
Vote

0% completed

​

Palindrome Check using Queue (easy)

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

.....

.....

.....

Like the course? Get enrolled and start learning!
An Van

An Van

· 3 years ago

I realized after taking this that there are different built in library or premade library to make deque easier, maybe it good to explain the library as well

Show 1 reply
G

grjkatr

· 2 years ago

# The initial soluton did is incorrect. A queue should only remove elements from either the front or the end but not both.

function isPalindrome(s: string): boolean {
    // Normalize the string: convert to lowercase and remove non-alphanumeric characters
    const normalizedStr = s.replace(/[^a-zA-Z0-9]/g, '').toLowerCase();

    // Initialize a queue (array used as a queue) and a stack
    const queue: string[] = [];
    const stack: string[] = [];

    // Add each character of the normalized string to both the queue and the stack
    for (const char of normalizedStr) {
        queue.push(char);
        stack.push(char);
    }

    // Check if the string is a palindrome using the queue and the stack
    while (queue.length > 0) {
        if (queue.shift() !== stack.pop())
Rohit Ranjan

Rohit Ranjan

· a year ago

My code passed!! But it shouldn't pass for string: "ra4d5ar".

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
bool checkPalindrome(string s) {
        queue<char> q; string str{};
        for(char c: s){
            if(c>='a' && c<='z'){
                str += c;
            }
            else if(c>='A' && c<='Z'){
                str += (c+32);
            }
        }
        for(char c : str){
            q.push(c);
        }

        for(int i=str.length()-1; i>0; i--){
            char ch1 = str[i];
            char ch2 = q.front();
            if(ch1 != ch2){
                return false;
            }
            q.pop();
        }
        return true;
    }
};
Erik Gutschmidt

Erik Gutschmidt

· a year ago

// This solution just checks if the first and last letters in the word are the same, which results in the Deque's size being smaller than the original length of the string. While this is certainly incorrect, it is still able to pass all test cases (as of 06/26/2025). If you try it with, for example, "snacks", the "if" statement will poll the ends of the Deque for each 's' on the ends of "snacks", causing myDeq.size() to shrink by 2. This results the return statement being true, even though "snacks" is not a palindrome.

import java.util.*;

public class Solution {

    public static boolean checkPalindrome(String s) {
        // ToDo: Write Your Code Here.
        Deque<Character> myDeq = new LinkedList<>();
        for(int i = 0; i < s.length(); i++){
            myDeq.addFi