Start learning free

LESSON 251 OF 414 · TWO POINTERS

Palindrome Check in Rust: Two Pointers on a Vec of Chars

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 9
    Ctrl + Enter to check

    RUST · TWO POINTERS

    Palindrome Check in Rust, explained

    Problem overview

    The function is_palindrome receives a String named input and returns true when the text reads the same backward as forward, and false otherwise. Every character counts, spaces included.

    The string "madam racecar madam" is a palindrome: reversed, it gives the same text, so the answer is true. The string "abcbx" starts with a and ends with x, so the answer is false.

    Approach: compare from both ends

    The easy way to test for a palindrome is to build the reversed text and compare it with the original. That works, but it needs a full second copy and does more work than necessary. A palindrome has a simpler description: the first character equals the last one, the second equals the second to last, and so on up to the middle.

    That suggests two pointers. Put left at the first character and right at the last. While left is before right, compare the two characters. If they differ, the answer is false at once. If they match, move left one step right and right one step left, and repeat. When the pointers meet or cross, every pair has matched, and the answer is true.

    For "abcbx", the first comparison is a against x. They differ, so the function returns false after a single check. For "abcba" the pairs a, a and b, b match, then the pointers meet on the middle c. That middle character is never compared, which is fine because it matches itself.

    Step by step

    1. Collect the characters into a vector. Rust strings can't be indexed by position, so input.chars().collect() builds a Vec<char>. The annotation Vec<char> tells collect which collection to build.
    2. Store the length in n with chars.len(). It is a usize, the unsigned type for sizes and indexes.
    3. Handle the empty string with an early return true when n == 0. An empty text reads the same backward. The return also protects the next step.
    4. Create left as a mutable usize at 0. The suffix on 0usize gives the literal its type.
    5. Create right as a mutable variable at n - 1, the last index. On an empty string this would underflow, because a usize can't go below zero. That is why step 3 comes first.
    6. Loop while left < right. As long as the pointers haven't met, there is a pair left to compare.
    7. Compare the pair. If chars[left] != chars[right], return false. One mismatch settles the question.
    8. Move both pointers inward: add 1 to left and subtract 1 from right. Without this, the loop would examine the same pair forever.
    9. Finish with true as the last expression, with no semicolon. It is reached only when every pair matched.

    The solution in Rust

    impl Solution {
    fn is_palindrome(input: String) -> bool {
        let chars: Vec<char> = input.chars().collect();
        let n = chars.len();
        if n == 0 {
            return true;
        }
        let mut left = 0usize;
        let mut right = n - 1;
        while left < right {
            if chars[left] != chars[right] {
                return false;
            }
            left += 1;
            right -= 1;
        }
        true
    }
}

    The Rust details worth a closer look:

    • Why not index the string? Writing input[0] on a String doesn't compile. The compiler reports the type `str` cannot be indexed by `{integer}`. A Rust string is UTF-8 text, and one character can take several bytes, so a position in bytes is not a position in characters.
    • Characters versus bytes. For "été", len() is 5 bytes but chars().count() is 3 characters. Collecting chars() gives a vector with one char per character, so the two pointers compare whole characters, and "été" is correctly a palindrome.
    • collect() needs a type. It can build many kinds of collections, so the annotation on chars is what selects Vec<char>.
    • Unsigned pointers. Both pointers are usize. The loop condition left < right guarantees that right is at least 1 when right -= 1 runs, so the subtraction can't go below zero.
    • Comparing chars. char implements !=, so chars[left] != chars[right] compares two values directly. No borrowing or cloning is needed, because char is a small Copy type.
    • Early return versus the last expression. Leaving the function from inside a loop needs return. The final true has no semicolon, so it is the function's value.

    Complexity

    Time: O(n). Building the vector takes one pass. The loop then runs at most n / 2 times, with constant work in each.

    Space: O(n). The vector of characters holds one entry per character. The pointers use constant space. A version that walks the string's characters from both ends with chars() and next_back() avoids the vector and needs only O(1) extra space.

    Edge cases and common mistakes

    • Empty string. It returns true from the early return. Without that return, n - 1 would underflow: it panics in a debug build and wraps in an optimized one.
    • One character. "a" gives true: left and right both start at 0, so the loop doesn't run.
    • Two characters. "ab" gives false and "aa" gives true. One comparison decides each.
    • Spaces and case count. "a b a" is a palindrome, but "aa " is not, because the trailing space has no partner. "Aba" is not a palindrome either, since A and a are different characters.
    • Non-ASCII text. "日本日" gives true, because the comparison is between characters rather than bytes.
    • Using left <= right. For "a" both pointers start at 0, the loop body runs, and right -= 1 subtracts 1 from a usize that holds 0. A debug build panics there, and an optimized build wraps to a huge value. The strict comparison avoids it.
    • Forgetting to move the pointers. The loop would repeat the same comparison forever when the pair matches.

    Testing

    • "madam racecar madam" gives true.
    • "abcbx" gives false.
    • "" gives true.
    • "abba" gives true.
    • "Aba" 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