Check Whether a String Is a Palindrome

A palindrome is a string that reads identically when its characters are reversed: “racecar” stays “racecar”, “hello” becomes “olleh”.

The check appears in placement tests across service-tier and product-tier companies, from AMCAT Automata rounds to technical interviews at mid-size IT firms. Three implementation strategies cover every variant an interviewer can ask.

What Makes a String a Palindrome

A string S of length n is a palindrome if and only if S[i] == S[n-1-i] for every index i from 0 to n/2 - 1. The character at position i from the left must equal the character at position i from the right.

Three worked examples illustrate the range of inputs:

• “racecar” (length 7): r==r at positions 0 and 6, a==a at positions 1 and 5, c==c at positions 2 and 4, middle ‘e’ at position 3 has no pair. Palindrome.
• “hello” (length 5): ‘h’ at position 0 vs ‘o’ at position 4. Mismatch at the first comparison. Not a palindrome.
• “A man a plan a canal Panama”: as-is, with spaces and mixed case, not a palindrome. After stripping non-alphanumeric characters and lowercasing: “amanaplanacanalpanama”. Reversed: “amanaplanacanalpanama”. They match. Palindrome.

The third example is the most common follow-up in technical interviews. Candidates who have only practised the basic case-sensitive version will stall here; those who understood the preprocessing step will not.

Approach 1: Two-Pointer Check

Two indices start at opposite ends of the string and walk toward each other. If any pair of characters mismatches, the string is not a palindrome. If the pointers cross without a mismatch, it is.

Algorithm

• Set left = 0, right = n - 1.
• While left < right:
  • If s[left] != s[right], return false.
  • Increment left, decrement right.
• Return true.

C Code

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

bool isPalindrome(const char *s) {
    int left = 0, right = (int)strlen(s) - 1;
    while (left < right) {
        if (s[left] != s[right]) return false;
        left++;
        right--;
    }
    return true;
}

int main() {
    printf("%s\n", isPalindrome("racecar") ? "Palindrome" : "Not a palindrome");
    printf("%s\n", isPalindrome("hello")   ? "Palindrome" : "Not a palindrome");
    return 0;
}

C++ Code

#include <iostream>
#include <string>
using namespace std;

bool isPalindrome(const string &s) {
    int left = 0, right = (int)s.size() - 1;
    while (left < right) {
        if (s[left] != s[right]) return false;
        left++;
        right--;
    }
    return true;
}

int main() {
    cout << (isPalindrome("racecar") ? "Palindrome" : "Not a palindrome") << "\n";
    cout << (isPalindrome("hello")   ? "Palindrome" : "Not a palindrome") << "\n";
    return 0;
}

Trace Through “racecar”

• Start: left=0 (‘r’), right=6 (‘r’). Match. Advance.
• left=1 (‘a’), right=5 (‘a’). Match. Advance.
• left=2 (‘c’), right=4 (‘c’). Match. Advance.
• left=3, right=3: left < right is false. Loop ends.
• Result: palindrome.

Complexity

• Time: O(n) — at most n/2 iterations, one comparison each.
• Space: O(1) — two integer indices regardless of string length.

This is the approach to state first in any placement interview that asks for the most efficient solution.

Approach 2: Reverse and Compare

Build a reversed copy of the string, then compare it with the original. More lines to write, and O(n) extra space, but the code reads naturally and is idiomatic in Python and Java.

Python

The Python documentation covers slice notation in the sequence operations section. The slice s[::-1] steps through s from the end to the start, producing a reversed copy in one expression:

def is_palindrome(s: str) -> bool:
    return s == s[::-1]

print(is_palindrome("racecar"))  # True
print(is_palindrome("hello"))    # False

Java

Java strings are immutable, so a reversed copy requires StringBuilder.reverse():

public class PalindromeCheck {
    public static boolean isPalindrome(String s) {
        String reversed = new StringBuilder(s).reverse().toString();
        return s.equals(reversed);
    }

    public static void main(String[] args) {
        System.out.println(isPalindrome("racecar")); // true
        System.out.println(isPalindrome("hello"));   // false
    }
}

Note: use .equals(), not ==. In Java, == compares object references. Two different String objects containing “racecar” will pass .equals() but may fail ==.

C++ with std::reverse

std::reverse from <algorithm> reverses a range in place:

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

bool isPalindrome(string s) {
    string rev = s;
    reverse(rev.begin(), rev.end());
    return s == rev;
}

int main() {
    cout << (isPalindrome("racecar") ? "Palindrome" : "Not a palindrome") << "\n";
    cout << (isPalindrome("hello")   ? "Palindrome" : "Not a palindrome") << "\n";
    return 0;
}

Complexity

• Time: O(n) — one pass to reverse, one pass to compare.
• Space: O(n) — the reversed copy occupies memory proportional to the string length.

In an interview, always state the space cost difference between this approach and the two-pointer. Both are O(n) in time; only this one uses O(n) space.

Approach 3: Recursive Check

The recursive version expresses the same two-pointer logic via function calls instead of a loop. Each call checks one character pair and recurses on the inner substring.

Java (Recursive)

public class RecursivePalindrome {
    public static boolean isPalindrome(String s, int left, int right) {
        if (left >= right) return true;
        if (s.charAt(left) != s.charAt(right)) return false;
        return isPalindrome(s, left + 1, right - 1);
    }

    public static void main(String[] args) {
        String s = "racecar";
        System.out.println(isPalindrome(s, 0, s.length() - 1)); // true
    }
}

Complexity

• Time: O(n) — each character pair is checked exactly once.
• Space: O(n) — the recursion depth reaches n/2 before the base case fires, keeping up to n/2 stack frames active simultaneously.

The space cost is the only material difference from the iterative version. State it explicitly when comparing the two.

Case-Insensitive and Phrase Palindromes

The case-insensitive variant adds a preprocessing step: normalise the string before running any of the checks above.

Python (Case-Insensitive with Non-Alphanumeric Stripping)

def is_phrase_palindrome(s: str) -> bool:
    cleaned = ''.join(c.lower() for c in s if c.isalnum())
    return cleaned == cleaned[::-1]

print(is_phrase_palindrome("A man a plan a canal Panama"))  # True
print(is_phrase_palindrome("Madam"))                        # True
print(is_phrase_palindrome("hello"))                        # False

C++ (Case-Insensitive Two-Pointer)

#include <iostream>
#include <string>
#include <cctype>
using namespace std;

bool isCaseInsensitivePalindrome(const string &s) {
    int left = 0, right = (int)s.size() - 1;
    while (left < right) {
        if (tolower(s[left]) != tolower(s[right])) return false;
        left++;
        right--;
    }
    return true;
}

int main() {
    cout << (isCaseInsensitivePalindrome("Madam") ? "Palindrome" : "Not a palindrome") << "\n";
    return 0;
}

The phrase palindrome variant is the edge case that separates placement-ready candidates from those who only practised the basic version. The preprocessing (lowercase conversion and non-alphanumeric removal) is one line in Python and a tolower call inside the two-pointer loop in C or C++.

Complexity Summary

Approach	Time	Space	Languages
Two-pointer	O(n)	O(1)	C, C++
Reverse-and-compare	O(n)	O(n)	Python, Java, C++
Recursive	O(n)	O(n)	Java
Case-insensitive two-pointer	O(n)	O(1)	Python, C++

Where This Appears in Placement Tests

String palindrome turns up in three distinct placement contexts:

• AMCAT Automata: one of the most common coding question types at the easy-to-medium level. The basic case-sensitive version appears most often; the phrase variant with space and case handling appears occasionally as a harder variant.
• Technical interview screens: service-tier companies and mid-size IT firms use it as a warm-up in the first technical round. The interviewer then extends the problem: make it case-insensitive, handle spaces, handle a number input. Each extension tests whether the candidate understood the algorithm or just memorised the code.
• Product-company first rounds: the recursive variant and the space-complexity question are more common here. The interviewer may ask the candidate to compare iterative and recursive space costs explicitly.

The two-pointer pattern, with left and right converging from opposite ends, is the same structure used in problems like two-sum with sorted arrays and container with most water. For a broader set of string and array problems that appear across Indian placement tests, see 20 most asked data structures interview questions.

The single-pass convergence logic from Approach 1 shows up beyond placement prep. Scoring and ranking functions in LLM evaluation pipelines use the same pattern: compare sequences position by position, short-circuit on the first mismatch. TinkerLLM at ₹299 builds that connection through exercises that start from string-comparison problems like this one and progress toward sequence evaluation in language model outputs.

For another single-pass traversal problem in the same cluster, see find smallest and largest element in an array.