264 Fundamental

String Anagram Check

String Processing

Tutorial Video

Text description (accessibility)

This video demonstrates the "String Anagram Check" functional Rust example. Difficulty level: Fundamental. Key concepts covered: String Processing. Check if two strings are anagrams — they use exactly the same letters in a different arrangement. Key difference from OCaml: 1. **String to chars:** OCaml uses `String.to_seq |> List.of_seq`; Rust uses `.chars().collect::<Vec<_>>()`

Tutorial

The Problem

Check if two strings are anagrams — they use exactly the same letters in a different arrangement. Also find all anagrams of a word from a list of candidates.

🎯 Learning Outcomes

• String transformation with to_lowercase() and character iteration

• Two approaches: sorting-based (O(n log n)) and frequency-counting (O(n))

• Using closures as local helper functions

• Filtering with iterator adapters and lifetime annotations

🦀 The Rust Way

Rust offers two idiomatic approaches: sorting a Vec<char> (mirrors OCaml) or counting character frequencies with a HashMap. The iterator-based filter with find_anagrams parallels OCaml's List.filter.

Code Example

pub fn is_anagram_sort(s1: &str, s2: &str) -> bool {
    let normalize = |s: &str| -> String { s.to_lowercase() };
    let sorted_chars = |s: &str| -> Vec<char> {
        let mut chars: Vec<char> = s.to_lowercase().chars().collect();
        chars.sort_unstable();
        chars
    };
    normalize(s1) != normalize(s2) && sorted_chars(s1) == sorted_chars(s2)
}

pub fn find_anagrams<'a>(word: &str, candidates: &[&'a str]) -> Vec<&'a str> {
    candidates.iter().copied().filter(|c| is_anagram_sort(word, c)).collect()
}

let to_sorted_chars s =
  s |> String.lowercase_ascii
    |> String.to_seq |> List.of_seq
    |> List.sort Char.compare

let is_anagram s1 s2 =
  let s1' = String.lowercase_ascii s1 in
  let s2' = String.lowercase_ascii s2 in
  s1' <> s2' && to_sorted_chars s1 = to_sorted_chars s2

let find_anagrams word candidates =
  List.filter (is_anagram word) candidates

Key Differences

String to chars: OCaml uses String.to_seq |> List.of_seq; Rust uses .chars().collect::<Vec<_>>()

Sorting: OCaml sorts a linked list (O(n log n)); Rust sorts a Vec in-place with sort_unstable

Frequency counting: Not idiomatic in OCaml stdlib; Rust's HashMap makes O(n) solution natural

Lifetimes: Rust's find_anagrams needs 'a lifetime to borrow candidate strings from the input slice

OCaml Approach

OCaml converts strings to character lists via String.to_seq |> List.of_seq, sorts them with List.sort Char.compare, and compares. The pipeline operator |> chains the transformations cleanly.

Full Source

#![allow(clippy::all)]
//! String Anagram Check
//!
//! OCaml: sorts character lists and compares.
//! Rust: can use sorted Vec<char> or frequency counting with a HashMap.
//!
//! An anagram uses exactly the same letters in a different arrangement.
//! Two strings are anagrams if they have the same letter frequencies
//! but are not identical (case-insensitive).

//! Solution 1: Idiomatic Rust — sort characters and compare.
//! Mirrors the OCaml approach closely.
pub fn is_anagram_sort(s1: &str, s2: &str) -> bool {
    let normalize = |s: &str| -> String { s.to_lowercase() };
    let sorted_chars = |s: &str| -> Vec<char> {
        let mut chars: Vec<char> = s.to_lowercase().chars().collect();
        chars.sort_unstable();
        chars
    };
    normalize(s1) != normalize(s2) && sorted_chars(s1) == sorted_chars(s2)
}

/// Solution 2: Frequency counting — O(n) using a HashMap.
/// More efficient than sorting for long strings.
pub fn is_anagram_freq(s1: &str, s2: &str) -> bool {
    use std::collections::HashMap;

    let lower1 = s1.to_lowercase();
    let lower2 = s2.to_lowercase();
    if lower1 == lower2 {
        return false;
    }

    let freq = |s: &str| -> HashMap<char, i32> {
        let mut map = HashMap::new();
        for c in s.chars() {
            *map.entry(c).or_insert(0) += 1;
        }
        map
    };
    freq(&lower1) == freq(&lower2)
}

/// Finds all anagrams of `word` in a list of candidates.
/// OCaml: `let find_anagrams word candidates = List.filter (is_anagram word) candidates`
pub fn find_anagrams<'a>(word: &str, candidates: &[&'a str]) -> Vec<&'a str> {
    candidates
        .iter()
        .copied()
        .filter(|c| is_anagram_sort(word, c))
        .collect()
}

/// Functional/iterator approach: find anagrams using the freq method.
pub fn find_anagrams_freq<'a>(word: &str, candidates: &[&'a str]) -> Vec<&'a str> {
    candidates
        .iter()
        .copied()
        .filter(|c| is_anagram_freq(word, c))
        .collect()
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_basic_anagram() {
        assert!(is_anagram_sort("listen", "silent"));
        assert!(is_anagram_freq("listen", "silent"));
    }

    #[test]
    fn test_not_anagram() {
        assert!(!is_anagram_sort("hello", "world"));
        assert!(!is_anagram_freq("hello", "world"));
    }

    #[test]
    fn test_same_word_not_anagram() {
        // A word is not an anagram of itself
        assert!(!is_anagram_sort("listen", "listen"));
        assert!(!is_anagram_freq("listen", "listen"));
    }

    #[test]
    fn test_case_insensitive() {
        assert!(is_anagram_sort("Listen", "Silent"));
        assert!(is_anagram_freq("Listen", "Silent"));
    }

    #[test]
    fn test_different_lengths() {
        assert!(!is_anagram_sort("abc", "abcd"));
        assert!(!is_anagram_freq("abc", "abcd"));
    }

    #[test]
    fn test_find_anagrams() {
        let results = find_anagrams("listen", &["enlists", "google", "inlets", "silent"]);
        assert_eq!(results, vec!["inlets", "silent"]);
    }

    #[test]
    fn test_find_anagrams_freq() {
        let results = find_anagrams_freq("listen", &["enlists", "google", "inlets", "silent"]);
        assert_eq!(results, vec!["inlets", "silent"]);
    }

    #[test]
    fn test_empty_strings() {
        // Two empty strings are equal, not anagrams
        assert!(!is_anagram_sort("", ""));
        assert!(!is_anagram_freq("", ""));
    }
}

let to_sorted_chars s =
  s |> String.lowercase_ascii
    |> String.to_seq |> List.of_seq
    |> List.sort Char.compare

let is_anagram s1 s2 =
  let s1' = String.lowercase_ascii s1 in
  let s2' = String.lowercase_ascii s2 in
  s1' <> s2' && to_sorted_chars s1 = to_sorted_chars s2

let find_anagrams word candidates =
  List.filter (is_anagram word) candidates

let () =
  assert (is_anagram "listen" "silent" = true);
  assert (is_anagram "hello" "world" = false);
  assert (is_anagram "listen" "listen" = false);
  let results = find_anagrams "listen" ["enlists";"google";"inlets";"silent"] in
  assert (results = ["inlets";"silent"]);
  print_endline "ok"

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_basic_anagram() {
        assert!(is_anagram_sort("listen", "silent"));
        assert!(is_anagram_freq("listen", "silent"));
    }

    #[test]
    fn test_not_anagram() {
        assert!(!is_anagram_sort("hello", "world"));
        assert!(!is_anagram_freq("hello", "world"));
    }

    #[test]
    fn test_same_word_not_anagram() {
        // A word is not an anagram of itself
        assert!(!is_anagram_sort("listen", "listen"));
        assert!(!is_anagram_freq("listen", "listen"));
    }

    #[test]
    fn test_case_insensitive() {
        assert!(is_anagram_sort("Listen", "Silent"));
        assert!(is_anagram_freq("Listen", "Silent"));
    }

    #[test]
    fn test_different_lengths() {
        assert!(!is_anagram_sort("abc", "abcd"));
        assert!(!is_anagram_freq("abc", "abcd"));
    }

    #[test]
    fn test_find_anagrams() {
        let results = find_anagrams("listen", &["enlists", "google", "inlets", "silent"]);
        assert_eq!(results, vec!["inlets", "silent"]);
    }

    #[test]
    fn test_find_anagrams_freq() {
        let results = find_anagrams_freq("listen", &["enlists", "google", "inlets", "silent"]);
        assert_eq!(results, vec!["inlets", "silent"]);
    }

    #[test]
    fn test_empty_strings() {
        // Two empty strings are equal, not anagrams
        assert!(!is_anagram_sort("", ""));
        assert!(!is_anagram_freq("", ""));
    }
}

Deep Comparison

OCaml vs Rust: String Anagram Check

Side-by-Side Code

OCaml

let to_sorted_chars s =
  s |> String.lowercase_ascii
    |> String.to_seq |> List.of_seq
    |> List.sort Char.compare

let is_anagram s1 s2 =
  let s1' = String.lowercase_ascii s1 in
  let s2' = String.lowercase_ascii s2 in
  s1' <> s2' && to_sorted_chars s1 = to_sorted_chars s2

let find_anagrams word candidates =
  List.filter (is_anagram word) candidates

Rust (idiomatic — sort-based)

pub fn is_anagram_sort(s1: &str, s2: &str) -> bool {
    let normalize = |s: &str| -> String { s.to_lowercase() };
    let sorted_chars = |s: &str| -> Vec<char> {
        let mut chars: Vec<char> = s.to_lowercase().chars().collect();
        chars.sort_unstable();
        chars
    };
    normalize(s1) != normalize(s2) && sorted_chars(s1) == sorted_chars(s2)
}

pub fn find_anagrams<'a>(word: &str, candidates: &[&'a str]) -> Vec<&'a str> {
    candidates.iter().copied().filter(|c| is_anagram_sort(word, c)).collect()
}

Rust (functional — frequency counting)

pub fn is_anagram_freq(s1: &str, s2: &str) -> bool {
    use std::collections::HashMap;
    let lower1 = s1.to_lowercase();
    let lower2 = s2.to_lowercase();
    if lower1 == lower2 { return false; }
    let freq = |s: &str| -> HashMap<char, i32> {
        let mut map = HashMap::new();
        for c in s.chars() { *map.entry(c).or_insert(0) += 1; }
        map
    };
    freq(&lower1) == freq(&lower2)
}

Type Signatures

Concept	OCaml	Rust
Anagram check	`val is_anagram : string -> string -> bool`	`fn is_anagram_sort(s1: &str, s2: &str) -> bool`
Find anagrams	`val find_anagrams : string -> string list -> string list`	`fn find_anagrams<'a>(word: &str, candidates: &[&'a str]) -> Vec<&'a str>`
Sorted chars	`val to_sorted_chars : string -> char list`	closure: `\|s: &str\| -> Vec<char>`
String type	`string` (immutable)	`&str` (borrowed slice)

Key Insights

Pipeline vs method chains: OCaml's |> operator chains String.to_seq |> List.of_seq |> List.sort; Rust chains .chars().collect() then .sort_unstable() — same idea, different syntax

Closures as helpers: Both languages use local functions/closures for sorted_chars; Rust closures capture nothing here (pure transformations)

Lifetime annotations: Rust's find_anagrams returns Vec<&'a str> — the compiler needs to know the returned references live as long as the input candidates. OCaml's GC handles this implicitly

HashMap for O(n): Rust's standard library makes frequency counting natural with HashMap::entry; OCaml's stdlib doesn't have a convenient hash map for this pattern

In-place sorting: Rust sorts Vec<char> in-place (no allocation); OCaml creates a new sorted list

When to Use Each Style

Use sort-based when: strings are short and code clarity matters more than performance Use frequency-counting when: strings are long or you're doing many comparisons — O(n) beats O(n log n)

Exercises

Generalize is_anagram to work on any Iterator<Item=char> rather than &str, enabling anagram detection over character streams.

Implement group_anagrams that takes a list of words and groups them into buckets where each bucket contains words that are anagrams of each other.

Build a fast anagram index: preprocess a large word list into a HashMap<String, Vec<String>> mapping sorted-letter keys to matching words, then look up all anagrams of a query word in O(k log k) time (k = word length).

Open Source Repos

functional-rust

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

Rust