791 Advanced

791-palindrome-partitioning — Palindrome Partitioning

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "791-palindrome-partitioning — Palindrome Partitioning" functional Rust example. Difficulty level: Advanced. Key concepts covered: Functional Programming. Palindrome partitioning asks: what is the minimum number of cuts needed to divide a string into parts where each part is a palindrome? Key difference from OCaml: 1. **Two

Tutorial

The Problem

Palindrome partitioning asks: what is the minimum number of cuts needed to divide a string into parts where each part is a palindrome? This combines two DP subproblems: checking if substrings are palindromes (interval DP) and finding minimum cuts (linear DP). It appears in DNA restriction site analysis, string compression algorithms, and has connections to the Longest Palindromic Subsequence problem.

🎯 Learning Outcomes

• Pre-compute a 2D boolean table is_pal[i][j] for all substring palindrome checks

• Use the palindrome expansion technique: is_pal[i][j] = chars[i]==chars[j] && is_pal[i+1][j-1]

• Apply minimum cuts DP: dp[i] = min over j: dp[j-1] + 1 when is_pal[j][i]

• Understand the O(n²) time complexity for both the palindrome check and the cuts DP

• See how this combines interval DP (palindrome table) with linear DP (cuts)

Code Example

#![allow(clippy::all)]
//! # Palindrome Partitioning

pub fn min_cuts(s: &str) -> usize {
    let chars: Vec<char> = s.chars().collect();
    let n = chars.len();
    if n <= 1 {
        return 0;
    }

    let mut is_pal = vec![vec![false; n]; n];
    for i in 0..n {
        is_pal[i][i] = true;
    }
    for i in 0..n - 1 {
        is_pal[i][i + 1] = chars[i] == chars[i + 1];
    }
    for len in 3..=n {
        for i in 0..=n - len {
            let j = i + len - 1;
            is_pal[i][j] = chars[i] == chars[j] && is_pal[i + 1][j - 1];
        }
    }

    let mut dp = vec![0; n];
    for i in 0..n {
        if is_pal[0][i] {
            dp[i] = 0;
        } else {
            dp[i] = i;
            for j in 1..=i {
                if is_pal[j][i] {
                    dp[i] = dp[i].min(dp[j - 1] + 1);
                }
            }
        }
    }
    dp[n - 1]
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_cuts() {
        assert_eq!(min_cuts("aab"), 1);
    }
    #[test]
    fn test_palindrome() {
        assert_eq!(min_cuts("aa"), 0);
    }
}

(* Palindrome Partitioning — minimum cuts DP O(n²) *)

let palindrome_partition s =
  let n = String.length s in
  if n = 0 then (0, [])
  else begin
    (* is_pal.(i).(j) = true if s[i..j] is palindrome *)
    let is_pal = Array.make_matrix n n false in
    (* Single chars *)
    for i = 0 to n - 1 do is_pal.(i).(i) <- true done;
    (* Length 2 *)
    for i = 0 to n - 2 do
      is_pal.(i).(i+1) <- s.[i] = s.[i+1]
    done;
    (* Length 3+ *)
    for len = 3 to n do
      for i = 0 to n - len do
        let j = i + len - 1 in
        is_pal.(i).(j) <- s.[i] = s.[j] && is_pal.(i+1).(j-1)
      done
    done;

    (* cuts.(i) = min cuts for s[0..i] *)
    let cuts = Array.make n max_int in
    let prev = Array.make n (-1) in  (* where the last partition starts *)
    for i = 0 to n - 1 do
      if is_pal.(0).(i) then begin
        cuts.(i) <- 0;
        prev.(i) <- 0
      end else begin
        for j = 1 to i do
          if is_pal.(j).(i) then begin
            let c = cuts.(j-1) + 1 in
            if c < cuts.(i) then begin
              cuts.(i) <- c;
              prev.(i) <- j
            end
          end
        done
      end
    done;

    (* Reconstruct partitions *)
    let parts = ref [] in
    let j = ref (n - 1) in
    while !j >= 0 do
      let start = prev.(!j) in
      parts := String.sub s start (!j - start + 1) :: !parts;
      j := start - 1
    done;
    (cuts.(n-1), !parts)
  end

let () =
  let test s =
    let (cuts, parts) = palindrome_partition s in
    Printf.printf "s = %S -> cuts = %d, parts = [%s]\n"
      s cuts (String.concat "; " (List.map (Printf.sprintf "%S") parts))
  in
  test "aab";
  test "a";
  test "ab";
  test "aabb";
  test "racecaranana"

Key Differences

Two-phase DP: Both languages use the same two-phase approach (palindrome table then cuts); the structure is algorithm-determined, not language-determined.

Boundary conditions: Rust's dp[i] = i initialization bounds cuts; OCaml uses the same; careful initialization avoids off-by-one errors.

Combination: This problem requires combining two DP patterns — interval DP and linear DP — which is the same in both languages.

O(n) space improvement: Manacher's algorithm computes palindrome checks in O(n) time; combined with the cuts DP, achieves O(n) total space.

OCaml Approach

OCaml implements both DP tables with Array.make_matrix. The palindrome expansion is idiomatic with nested for loops. The minimum cuts DP uses Array.init for initialization and imperative updates. A recursive approach with memoization is also natural in OCaml: min_cuts s i = min over j in 0..i: [if is_pal s j i then 1 + min_cuts s (j-1) else infinity].

Full Source

#![allow(clippy::all)]
//! # Palindrome Partitioning

pub fn min_cuts(s: &str) -> usize {
    let chars: Vec<char> = s.chars().collect();
    let n = chars.len();
    if n <= 1 {
        return 0;
    }

    let mut is_pal = vec![vec![false; n]; n];
    for i in 0..n {
        is_pal[i][i] = true;
    }
    for i in 0..n - 1 {
        is_pal[i][i + 1] = chars[i] == chars[i + 1];
    }
    for len in 3..=n {
        for i in 0..=n - len {
            let j = i + len - 1;
            is_pal[i][j] = chars[i] == chars[j] && is_pal[i + 1][j - 1];
        }
    }

    let mut dp = vec![0; n];
    for i in 0..n {
        if is_pal[0][i] {
            dp[i] = 0;
        } else {
            dp[i] = i;
            for j in 1..=i {
                if is_pal[j][i] {
                    dp[i] = dp[i].min(dp[j - 1] + 1);
                }
            }
        }
    }
    dp[n - 1]
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_cuts() {
        assert_eq!(min_cuts("aab"), 1);
    }
    #[test]
    fn test_palindrome() {
        assert_eq!(min_cuts("aa"), 0);
    }
}

(* Palindrome Partitioning — minimum cuts DP O(n²) *)

let palindrome_partition s =
  let n = String.length s in
  if n = 0 then (0, [])
  else begin
    (* is_pal.(i).(j) = true if s[i..j] is palindrome *)
    let is_pal = Array.make_matrix n n false in
    (* Single chars *)
    for i = 0 to n - 1 do is_pal.(i).(i) <- true done;
    (* Length 2 *)
    for i = 0 to n - 2 do
      is_pal.(i).(i+1) <- s.[i] = s.[i+1]
    done;
    (* Length 3+ *)
    for len = 3 to n do
      for i = 0 to n - len do
        let j = i + len - 1 in
        is_pal.(i).(j) <- s.[i] = s.[j] && is_pal.(i+1).(j-1)
      done
    done;

    (* cuts.(i) = min cuts for s[0..i] *)
    let cuts = Array.make n max_int in
    let prev = Array.make n (-1) in  (* where the last partition starts *)
    for i = 0 to n - 1 do
      if is_pal.(0).(i) then begin
        cuts.(i) <- 0;
        prev.(i) <- 0
      end else begin
        for j = 1 to i do
          if is_pal.(j).(i) then begin
            let c = cuts.(j-1) + 1 in
            if c < cuts.(i) then begin
              cuts.(i) <- c;
              prev.(i) <- j
            end
          end
        done
      end
    done;

    (* Reconstruct partitions *)
    let parts = ref [] in
    let j = ref (n - 1) in
    while !j >= 0 do
      let start = prev.(!j) in
      parts := String.sub s start (!j - start + 1) :: !parts;
      j := start - 1
    done;
    (cuts.(n-1), !parts)
  end

let () =
  let test s =
    let (cuts, parts) = palindrome_partition s in
    Printf.printf "s = %S -> cuts = %d, parts = [%s]\n"
      s cuts (String.concat "; " (List.map (Printf.sprintf "%S") parts))
  in
  test "aab";
  test "a";
  test "ab";
  test "aabb";
  test "racecaranana"

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_cuts() {
        assert_eq!(min_cuts("aab"), 1);
    }
    #[test]
    fn test_palindrome() {
        assert_eq!(min_cuts("aa"), 0);
    }
}

Deep Comparison

OCaml vs Rust: Palindrome Partitioning

Overview

See the example.rs and example.ml files for detailed implementations.

Key Differences

Aspect	OCaml	Rust
Type system	Hindley-Milner	Ownership + traits
Memory	GC	Zero-cost abstractions
Mutability	Explicit ref	mut keyword
Error handling	Option/Result	Result<T, E>

See README.md for detailed comparison.

Exercises

Implement palindrome_partition_list(s) -> Vec<Vec<String>> that returns all valid palindrome partitions (exponential output), using backtracking on the precomputed is_pal table.

Use Manacher's algorithm (example 820) to compute the palindrome table in O(n) time, improving the total complexity.

Extend to minimum_palindrome_partition_k(s, k) — minimum cuts to get exactly k palindrome parts, adding a third dimension to the DP.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust