JuniorCodeVery commonNot answered yet
Check whether a string is a palindrome
Given a string, return true if it reads the same forwards and backwards.
Requirements:
- O(n) time, O(1) extra space (two pointers — do not reverse into a buffer).
- The empty string and a single character are valid palindromes.
#include <string>
bool isPalindrome(const std::string& s) {
// your code here
}Write the implementation.
Use two pointers starting at both ends, advancing toward the center. Compare characters; if they differ the string is not a palindrome. Time O(n), space O(1).
- ✗Reversing the whole string and comparing — allocates O(n) extra memory unnecessarily
- ✗Not handling case sensitivity or non-letter characters for real-world inputs
- ✗Using signed index arithmetic that can underflow when the string is empty
- →How would you check if a linked list is a palindrome?
- →What is the longest palindromic substring problem and what algorithm solves it efficiently?
Contents
Task
Write a function to check if a string is a palindrome (reads the same forwards and backwards).
Solution
bool isPalindrome(const std::string& s) {
int left = 0;
int right = static_cast<int>(s.size()) - 1;
while (left < right) {
if (s[left] != s[right]) return false;
++left; --right;
}
return true;
}Key points
- Two-pointer approach: O(n) time, O(1) space.
- For real-world inputs normalise first: lowercase + skip non-alphanumeric characters.
- Empty string and single character are valid palindromes.
Contents
