Topic 22 of 27 · Beginner
Check a byte-string palindrome without a reversed copy
Return whether a std::string reads identically in both byte directions.
BeginnerFreshers · 0 yearsStrings
C++20; compile with g++ -std=c++20.
Problem statement
Return whether a std::string reads identically in both byte directions.
A basic comparison exercise with explicit byte semantics.
Input: std::string.
Output: bool.
- No Unicode grapheme interpretation.
- Empty string is a palindrome.
Sample 1
Input: aba Output: true
Matching symmetric bytes.
Sample 2
Input: ab Output: false
Ends differ.
Brute-force solution
Copy and reverse the string then compare it.
O(n)
#include <string>
#include <iostream>
#include <cassert>
bool palindrome(const std::string& s){std::size_t i=0,j=s.size();while(i<j){--j;if(s[i++]!=s[j])return false;}return true;}
int main() {
assert(palindrome("aba"));assert(palindrome(""));assert(!palindrome("ab"));std::cout<<palindrome("aba")<<"\n";
return 0;
}
Optimized solution
Compare symmetric bytes with two indices and stop at the first mismatch.
- Use a half-open right boundary.
- Decrement before reading.
- Compare inward until crossed.
#include <string>
#include <iostream>
#include <cassert>
bool palindrome(const std::string& s){std::size_t i=0,j=s.size();while(i<j){--j;if(s[i++]!=s[j])return false;}return true;}
int main() {
assert(palindrome("aba"));assert(palindrome(""));assert(!palindrome("ab"));std::cout<<palindrome("aba")<<"\n";
return 0;
}
Complexity analysis
Time: O(n)
Auxiliary space: O(1)
Test cases
- Empty.
- One byte.
- Even length.
Supplied main asserts empty, palindrome and non-palindrome inputs.Common mistakes
- Unsigned underflow from size()-1 on an empty string.
- Claiming Unicode-aware comparison.
Key takeaways
- Use safe index bounds.
- Specify byte semantics.
- Avoid a reversed copy.
Follow-up challenges
- How would case-insensitive comparison differ?
- How would you compare normalized Unicode?