264: String Anagram Check

Difficulty: 1 Level: Beginner Two approaches to check if strings are anagrams — sort-and-compare (O(n log n)) and frequency counting (O(n)).

The Problem This Solves

You're building a word game, a spell checker, or a search feature that suggests rearrangements. You need to determine whether two words use the exact same letters in different orders: "listen" and "silent" are anagrams; "listen" and "enlist" are too. "listen" and "listens" are not. Without a built-in anagram check, you'd manually count character occurrences, handle case normalization, and compare frequency maps — all boilerplate that distracts from your actual problem. For filtering a list of candidates (the common real-world use case), you'd loop over each candidate and repeat the comparison logic. The sort-based approach mirrors functional programming idioms: transform both strings the same way, compare results. The frequency-count approach is more efficient for large strings. Knowing both gives you the right tool for each situation.

The Intuition

Two strings are anagrams if sorting their characters produces the same sequence — or equivalently, if they have identical character frequency maps.

How It Works in Rust

// Sort-based: O(n log n) — mirrors OCaml approach
pub fn is_anagram_sort(s1: &str, s2: &str) -> bool {
 let sorted_chars = |s: &str| -> Vec<char> {
     let mut chars: Vec<char> = s.to_lowercase().chars().collect();
     chars.sort_unstable();  // in-place sort, faster than sort()
     chars
 };
 // Same word is not an anagram of itself
 s1.to_lowercase() != s2.to_lowercase() && sorted_chars(s1) == sorted_chars(s2)
}

// Frequency-based: O(n) — no sorting, HashMap counts each char
pub fn is_anagram_freq(s1: &str, s2: &str) -> bool {
 use std::collections::HashMap;
 let freq = |s: &str| -> HashMap<char, i32> {
     let mut map = HashMap::new();
     for c in s.to_lowercase().chars() {
         *map.entry(c).or_insert(0) += 1;
     }
     map
 };
 s1.to_lowercase() != s2.to_lowercase() && freq(s1) == freq(s2)
}

// Filter candidates: the classic use case
pub fn find_anagrams<'a>(word: &str, candidates: &[&'a str]) -> Vec<&'a str> {
 candidates.iter().copied()
     .filter(|c| is_anagram_sort(word, c))
     .collect()
}
// 'a lifetime: candidates outlive the returned Vec — borrows, not copies

What This Unlocks

Word game engines: Scrabble-style solvers that find all valid words from a rack of letters.
Duplicate detection: Detecting near-duplicate records where fields are transposed or reordered.
Test data generation: Generating all permutations of a string programmatically using the same char-frequency foundation.

Key Differences

Concept	OCaml	Rust
String to chars	`String.to_seq \	> List.of_seq`	`.chars().collect::<Vec<char>>()`
Sort	`List.sort Char.compare` (new list)	`.sort_unstable()` (in-place, faster)
Frequency map	Manual fold with `Map`	`HashMap` with `.entry().or_insert(0)`
Borrowing candidates	N/A (GC manages)	`'a` lifetime ties return to input slice
Pipeline	`\	>` operator	Method chaining `.filter().collect()`

/// String Anagram Check — Sorting and Frequency Counting Approaches

/// Sort-based: mirrors OCaml's approach.
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)
}

/// Frequency-based: O(n) using HashMap.
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)
}

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

fn main() {
    let results = find_anagrams("listen", &["enlists", "google", "inlets", "silent"]);
    println!("Anagrams of 'listen': {:?}", results);
    println!("is_anagram('listen', 'silent') = {}", is_anagram_sort("listen", "silent"));
    println!("is_anagram('listen', 'listen') = {}", is_anagram_sort("listen", "listen"));
}

/* Output:
   Anagrams of 'listen': ["inlets", "silent"]
   is_anagram('listen', 'silent') = true
   is_anagram('listen', 'listen') = false
*/

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"

📊 Detailed Comparison

OCaml vs Rust: String Anagram Check

Side-by-Side Code

OCaml

🐪 Show OCaml equivalent

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

1. 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 2. Closures as helpers: Both languages use local functions/closures for `sorted_chars`; Rust closures capture nothing here (pure transformations) 3. 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 4. 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 5. 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)