← C++ roadmap

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.

  1. Use a half-open right boundary.
  2. Decrement before reading.
  3. 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?
Practise C++ with the AI mentor

Can't find a C++ topic you need for exams or placements? Request it and we'll add it.