Start learning free

LESSON 254 OF 414 · TWO POINTERS

Palindrome Substrings in Rust: O(n²) by Expanding Around Centers

Practice O(n2) Read the full explanation

Given a string, count the number of palindromic contiguous substrings in the string.

The substrings with different start indexes or end indexes are counted as different substrings even if they consist of same characters.

Example:

Input:  "abbcbc"

Output: 9

Explanation: ["a", "b", "b", "c", "b", "c", "bb", "bcb", "cbc"]
STEP 1 OF 10
    Ctrl + Enter to check

    RUST · TWO POINTERS

    Palindrome Substrings in Rust, explained

    Problem overview

    The function count_palindromes takes a String and returns the number of contiguous substrings that read the same in both directions. Substrings with different start or end positions are different, even when their letters are equal. For "abbcbc" the answer is 9: the six single letters, plus "bb", "bcb" and "cbc".

    Approach: every palindrome has a center

    Testing every substring costs O(n³): about n²/2 substrings, and a check that may walk across most of each one. This lesson removes the repeated work with one observation: a palindrome is determined by its center and its radius. If the characters on both sides of a center match, extending by one more step on each side gives another palindrome. If they differ, no larger palindrome with that center exists, so the search from that center can stop.

    There are two kinds of centers:

    • An odd-length palindrome has one middle character, so its center is an index i, and the search starts with left = right = i.
    • An even-length palindrome has two middle characters, so its center sits between i and i + 1, and the search starts with left = i and right = i + 1.

    For each of the n positions, the code runs both searches. Each search counts one palindrome per successful expansion, which is why the count comes straight out of a loop with no extra bookkeeping. Every palindrome has exactly one center of exactly one kind, so none is counted twice.

    On "abbcbc": the odd searches give one palindrome for each of the six letters, plus "bcb" at index 3 and "cbc" at index 4, so 8. The even searches find only "bb" between indices 1 and 2. In total 8 + 1 = 9.

    Step by step

    1. Prepare. bytes is input.as_bytes(), a byte view for reading by index. n is input.len(), and result is a mutable counter, 0i32.
    2. Loop over centers with for i in 0..n.
    3. Odd centers. Call Self::count_with_center(bytes, i as i32, i as i32) and add its return value to result. The helper works with i32 indices, so i is converted with as i32.
    4. Even centers. Call the helper again with i as i32 and i as i32 + 1. If those two characters differ, it returns 0.
    5. Return result after the loop, with no semicolon.
    6. Declare the helper above count_palindromes. It takes bytes: &[u8] and two mut i32 indices, and returns the count. The indices are signed because left drops to -1 when the expansion passes the start of the string, and a usize cannot hold that.
    7. Start a counter named result at 0i32 inside the helper.
    8. Write the loop condition. Keep going while left >= 0, right is below bytes.len(), and the two bytes are equal. The checks run left to right and stop at the first false one, so the byte comparison, which indexes the slice, only runs when both indices are in range.
    9. Count and expand. Inside the loop, add 1 to result, then decrement left and increment right.
    10. Return result from the helper.

    The solution in Rust

    impl Solution {
    fn count_with_center(bytes: &[u8], mut left: i32, mut right: i32) -> i32 {
        let mut result = 0i32;
        while left >= 0
            && (right as usize) < bytes.len()
            && bytes[left as usize] == bytes[right as usize]
        {
            result += 1;
            left -= 1;
            right += 1;
        }
        result
    }
    fn count_palindromes(input: String) -> i32 {
        let bytes = input.as_bytes();
        let n = input.len();
        let mut result = 0i32;
        for i in 0..n {
            result += Self::count_with_center(bytes, i as i32, i as i32);
            result += Self::count_with_center(bytes, i as i32, i as i32 + 1);
        }
        result
    }
}

    Rust details worth knowing:

    • Why the order of the conditions matters. Casting a negative i32 with as usize does not fail: -1i32 as usize is 18446744073709551615. The check left >= 0 comes first so that a negative left ends the loop before it is ever cast or used to index.
    • Parentheses around right as usize. Without them, the compiler reads as usize < ... as the start of a generic type, like usize<...>, and reports a syntax error. Wrapping the cast in parentheses avoids that.
    • i as i32 + 1. The cast binds tighter than +, so this is (i as i32) + 1.
    • Bytes, not characters. The code compares bytes. For ASCII text that is the same as comparing characters. A two-byte letter like é gets treated as two separate bytes, so "éé" comes out as 6 instead of the 3 palindromes it has as text.
    • Tail expressions. result without a semicolon is what each function returns.

    Complexity

    Time: O(n²). There are 2n centers. An expansion can run up to about n/2 steps, as in a string of identical letters, and each step does constant work. In the typical case it stops much earlier.

    Space: O(1). The byte view shares the string's memory, and only a few integers are stored. This is a real improvement over the O(n³) time of testing every substring, with the same space.

    Edge cases and common mistakes

    • Empty string. The loop over centers doesn't run, and the result is 0.
    • Only odd centers. Forgetting the even call misses every palindrome with an even length. "abba" would give 4 instead of 6.
    • The last index as an even center. For i = n - 1, right is n, which is out of range. The check (right as usize) < bytes.len() turns that into a return of 0, instead of a panic.
    • Using usize for left. Decrementing a usize at 0 underflows. That panics in a debug build and wraps in an optimized one, which would make the next iteration index far outside the slice.
    • Checking bounds after indexing. Putting the byte comparison first reads out of range, and Rust panics. The comparison must stay last.
    • Repeated letters. "aaa" returns 6, and "aaaa" returns 10, because every window is a palindrome and each one is counted by its own center.

    Testing

    • "abbcbc" gives 9.
    • "aaa" gives 6.
    • "abc" gives 3.
    • "abba" gives 6.
    • "" gives 0.
    Keep going with RustAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free