Start learning free

LESSON 203 OF 414 · STRINGS

Palindrome Check in Rust: Reverse the String and Compare

Practice O(n) Read the full explanation

Given a string, determine if it is a palindrome.

A palindrome is a word, number, phrase, or other sequence of characters which reads the same backward as forward.

Example 1:

Input:  "madam racecar madam"

Output: true

Example 2:

Input:  "abcbx"

Output: false

Note:

Your algorithm should run in O(n) time and use O(1) extra space (the two-pointer approach below achieves this).


Hints:

For the string to be a palindrome, for each character, there is a corresponding element which should be equal to that one:
  • the character at index 0 equals the character at index n - 1
  • the character at index 1 equals the character at index n - 2
  • the character at index 2 equals the character at index n - 3
  • ...
How can we check all these pairs of corresponding characters while traversing the string one time?

We can use two pointers! One index variable i starting from the beginning (i = 0) and one index variable j starting from the end of the string (j = n - 1). How should we move these pointers through the algorithm?

For as long as i < j:
  • 1. We should check if the characters at indices i and j are different, and if so, we conclude the string is not a palindrome and return false.
  • 2. Move i one step to the right.
  • 3. Move j one step to the left.
  • 4. Go to step 1.
If i became greater than or equal to j and we haven't returned false, then we can conclude the string is a palindrome and return true.

STEP 1 OF 2
    Ctrl + Enter to check

    RUST · STRINGS

    Palindrome Check in Rust, explained

    Problem overview

    The function is_palindrome takes a String called input and returns a bool: true if the text reads the same forwards and backwards, false otherwise. Spaces count as characters, so "madam racecar madam" is a palindrome (reversed, it is the same text), and "abcbx" is not.

    Approach: build the reverse and compare

    The definition of a palindrome translates directly into code: reverse the string and see whether the result equals the original. If every character matches its mirror position, the reversed text is identical to the input. If any pair differs, the two strings differ.

    This is the most direct solution, and it is easy to get right. A two-pointer scan, comparing the first and last characters and moving inward, also works and avoids building a second string. That version is a different lesson. Here the focus is on Rust's iterator tools and on the idea that a comparison is already an answer.

    Step by step

    1. Build the reversed string. input.chars() walks the characters, rev() reverses the walk, and collect() gathers the characters into a new String called rev. The annotation : String on the variable is what tells collect() which kind of collection to build.
    2. Return the comparison. input == rev is true when the two strings hold the same characters in the same order, and false otherwise. Leave it as the last expression of the function, without a return keyword or a semicolon. No if is needed, because the comparison already is the bool to return.

    Tracing "abcbx": the reverse is "xbcba". The first characters differ, a against x, so the strings are not equal and the function returns false. For "abba" the reverse is "abba" and the answer is true.

    The solution in Rust

    impl Solution {
    fn is_palindrome(input: String) -> bool {
        let rev: String = input.chars().rev().collect();
        input == rev
    }
}

    Rust details worth knowing:

    • collect() is generic. The same method can build a Vec, a String, a HashMap and more. Rust picks one from the type you ask for. Without the : String annotation, the compiler can't tell and reports an error asking for a type.
    • == compares contents. For String values, == checks the characters, not where the strings live in memory. You don't need a special equals method.
    • The comparison borrows. Using == doesn't move input or rev. Both are only read.
    • Whole characters. chars() yields complete Unicode characters, so "été" is correctly seen as a palindrome. Reversing the bytes instead would split é into two pieces.
    • The tail expression. A line without a semicolon at the end of the function is its result. Writing input == rev; would make the function return () and the compiler would complain about the type.

    Complexity

    Time: O(n). Reversing walks the string once, and the comparison walks it once more. Both are linear in the length n.

    Space: O(n). The reversed copy is as long as the input. The statement asks for O(1) extra space, which the two-pointer scan achieves, but this version stores a second string, so it does not meet that bound.

    Edge cases and common mistakes

    • Empty string. The reverse of "" is "", so the function returns true.
    • One character. "a" is its own reverse, so the answer is true.
    • Case matters. "Madam" reverses to "madaM", so the function returns false. Making it case-insensitive would require converting the text to lower case first.
    • Spaces matter. "a b a" is a palindrome, but "ab a" is not, because its reverse is "a ba".
    • Missing annotation. let rev = input.chars().rev().collect(); doesn't compile, because nothing says what to collect into.
    • Comparing the wrong things. Comparing input with itself, or forgetting rev(), makes the answer always true.

    Testing

    • "madam racecar madam" gives true.
    • "abcbx" gives false.
    • "abba" gives true.
    • "" gives true.
    • "Madam" gives false.
    Keep going with RustAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free