LESSON 253 OF 414 · TWO POINTERS

Palindrome Substrings in Rust: Checking Every Substring

Practice O(n³) 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

Guided

Ctrl + Enter to check

RUST · TWO POINTERS

Palindrome Substrings in Rust, explained

Problem overview

The function count_palindromes takes a String and returns how many of its contiguous substrings read the same forwards and backwards. Substrings are counted by position, not by content: if the same text appears twice, at different places, it counts twice, and a single character is a palindrome of length 1.

For "abbcbc" the answer is 9. The six single characters are palindromes, and so are "bb", "bcb" and "cbc": 6 + 3 = 9.

Approach: try every start and end, then check

A substring is fixed by a start index i and an end index j with i <= j. This lesson takes the direct route: loop over every such pair, test whether the bytes from i to j form a palindrome, and add one to a counter when they do.

The test itself uses two pointers. Put one pointer on each end of the range and compare the bytes. If they differ, the range is not a palindrome. If they match, move both pointers inward and repeat. When the pointers meet or cross, every pair has matched, so the range is a palindrome. A range of length 1 starts with equal pointers and passes at once.

There are about n²/2 pairs and each check can take up to n/2 comparisons, so this version runs in O(n³). It is simple and correct, and it is the baseline that the next lesson on this problem improves by growing palindromes outward from their centers.

Step by step

Set up three values. n is the length of the input, bytes is a byte view from input.as_bytes() so that characters can be compared by index, and result is the counter, declared let mut as 0i32.
Loop over start indices with for i in 0..n. The range excludes n.
Loop over end indices with for j in i..n. Starting at i includes the one-character substring and never lets the end fall before the start.
Test and count. Call Self::is_palindrome_range(bytes, i, j), and add 1 to result when it returns true.
Return the counter as the final expression, with no semicolon.
Declare the helper above count_palindromes. It takes the byte slice and two indices, left and right, both mut because the loop moves them, and returns a bool.
Loop while left < right. Once they meet, the middle needs no comparison.
Return false on a mismatch. One differing pair is enough to rule the range out.
Move inward with left += 1 and right -= 1. The subtraction is safe because right is greater than left, so it is at least 1.
Return true after the loop. No mismatch means a palindrome.

The solution in Rust

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

Rust details worth knowing:

as_bytes() borrows. It returns a &[u8] that points into the string, so nothing is copied. The helper takes the slice type &[u8] and can read it but not change it.
mut on a parameter. mut left: usize makes the helper's own copy of the argument modifiable. The caller's i and j are not affected.
Self:: calls. The helper has no self parameter, so it is an associated function and is called as Self::is_palindrome_range(...).
Bytes, not characters. input.len() counts bytes. For ASCII text, one byte is one character and everything above holds. A letter such as é takes two bytes, so "éé" gets 6 from this code, although it has only 3 palindromic substrings as text: the two letters and the pair. Byte comparisons also find "palindromes" that cut a letter in half.
return versus the tail expression. The early return false leaves the helper from inside the loop. The closing true has no semicolon, so it is the value of the function.

Complexity

Time: O(n³). The two loops visit n(n + 1)/2 pairs. Each check compares up to (j - i + 1)/2 byte pairs. Summed over all pairs, that grows as n³. For a string of 2,000 equal letters, the work is already hundreds of millions of comparisons, while the answer, 2,001,000, fits comfortably in an i32.

Space: O(1). The byte view shares the string's memory, and the code stores a few integers.

Edge cases and common mistakes

Empty string. Both loops are empty and the function returns 0.
Single characters. A string of length n always has at least n palindromic substrings. "abc" has exactly 3, and "aaa" has 6: three singles, two pairs and the whole string.
Counting by content. Counting distinct texts would give a smaller number. In "aaa" there are only three distinct palindromes ("a", "aa", "aaa"), but the task wants 6.
Starting the inner loop at i + 1. This skips every single-character substring and undercounts by n.
Making the helper's condition left <= right. When both pointers are equal the extra round compares a byte with itself, which is harmless, but then right -= 1 can run with right at 0, which wraps in an optimized build and panics in a debug build. Keep the strict <.

Testing

"abbcbc" gives 9.
"aaa" gives 6.
"abc" gives 3.
"a" gives 1.
"" gives 0.
"aaaa" gives 10.

Keep going with RustAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free