062: Isogram Check

Difficulty: ⭐ Level: Foundations Detect whether a word has any repeating letters — a classic interview problem solved cleanly with a HashSet.

The Problem This Solves

You want to check for duplicate characters in a string. Maybe you're validating a crossword answer, building a word puzzle, or writing a coding challenge checker. The constraint is simple: every letter must appear exactly once. The brute-force way sorts the string and compares adjacent characters, or uses a nested loop. Both are clunky. In Python you'd write `len(set(word)) == len(word)`. JavaScript does similar with `Set`. Rust gives you two clean approaches: compare the length of a `HashSet` to the original count (simple), or use `HashSet::insert()` which returns `false` on duplicates and exit immediately (fast). The second approach is the more idiomatic Rust — it stops at the first problem rather than scanning everything.

The Intuition

`HashSet::insert()` returns a boolean: `true` if the value was new, `false` if it was already there. That one detail makes duplicate detection elegant — you don't need to check after the fact, you learn about duplicates the moment they happen. Python's `set` doesn't tell you whether insertion was new. You have to compare lengths afterward. Rust's API gives you the information exactly when you need it.

How It Works in Rust

Simple approach — compare set size to character count:

pub fn is_isogram(word: &str) -> bool {
 let letters: Vec<char> = word
     .chars()
     .filter(|c| c.is_ascii_alphabetic())  // ignore hyphens, spaces
     .map(|c| c.to_ascii_lowercase())
     .collect();
 let unique: HashSet<char> = letters.iter().copied().collect();
 letters.len() == unique.len()  // equal means no duplicates
}

Early-exit approach — stop at the first duplicate:

pub fn is_isogram_early_exit(word: &str) -> bool {
 let mut seen = HashSet::new();
 for c in word.chars() {
     if c.is_ascii_alphabetic() {
         // insert() returns false if already present
         if !seen.insert(c.to_ascii_lowercase()) {
             return false;
         }
     }
 }
 true
}

What This Unlocks

Duplicate detection — the same `insert() → false` pattern works for any type in any collection
Uniqueness constraints — validate that IDs, usernames, or configuration keys don't repeat
Interview problems — "find first repeated character", "check all unique" — all use this exact pattern

Key Differences

Concept	OCaml	Rust
Set insert	`Set.add` (always succeeds, returns new set)	`HashSet::insert()` returns `bool`
Early exit	`exception` or manual recursion	`return false` inside a loop
Immutability	OCaml sets are immutable values	`HashSet` is mutable, must declare `mut`
Length	`Set.cardinal`	`.len()`

/// # Isogram Check
///
/// An isogram is a word with no repeating letters (ignoring case, hyphens, spaces).
/// Demonstrates set-based duplicate detection.

use std::collections::HashSet;

/// Idiomatic Rust: filter to alphabetic, lowercase, check uniqueness via set size.
pub fn is_isogram(word: &str) -> bool {
    let letters: Vec<char> = word
        .chars()
        .filter(|c| c.is_ascii_alphabetic())
        .map(|c| c.to_ascii_lowercase())
        .collect();
    let unique: HashSet<char> = letters.iter().copied().collect();
    letters.len() == unique.len()
}

/// Early-exit approach: insert into set, return false on first duplicate.
/// More efficient for long strings with early duplicates.
pub fn is_isogram_early_exit(word: &str) -> bool {
    let mut seen = HashSet::new();
    for c in word.chars() {
        if c.is_ascii_alphabetic() {
            if !seen.insert(c.to_ascii_lowercase()) {
                return false; // insert returns false if already present
            }
        }
    }
    true
}

/// Bitflag approach — same idea as pangram but checking for collisions.
pub fn is_isogram_bitflag(word: &str) -> bool {
    let mut seen: u32 = 0;
    for c in word.chars() {
        if c.is_ascii_alphabetic() {
            let bit = 1 << (c.to_ascii_lowercase() as u32 - 'a' as u32);
            if seen & bit != 0 {
                return false;
            }
            seen |= bit;
        }
    }
    true
}

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

    #[test]
    fn test_isogram() {
        assert!(is_isogram("lumberjacks"));
        assert!(is_isogram("subdermatoglyphic"));
    }

    #[test]
    fn test_not_isogram() {
        assert!(!is_isogram("eleven"));
        assert!(!is_isogram("balloon")); // 'l' repeats
    }

    #[test]
    fn test_empty() {
        assert!(is_isogram(""));
    }

    #[test]
    fn test_hyphenated() {
        assert!(is_isogram("thumbscrew-japing"));
    }

    #[test]
    fn test_case_insensitive() {
        assert!(!is_isogram("Alphabet")); // 'a' appears twice
    }

    #[test]
    fn test_early_exit() {
        assert!(is_isogram_early_exit("lumberjacks"));
        assert!(!is_isogram_early_exit("eleven"));
    }

    #[test]
    fn test_bitflag() {
        assert!(is_isogram_bitflag("lumberjacks"));
        assert!(!is_isogram_bitflag("eleven"));
    }
}

(* Isogram Check — Detecting duplicate characters using a set *)

let is_isogram s =
  let chars = s |> String.lowercase_ascii |> String.to_seq
    |> Seq.filter (fun c -> c >= 'a' && c <= 'z')
    |> List.of_seq in
  let unique = List.sort_uniq Char.compare chars in
  List.length chars = List.length unique

(* Recursive approach with accumulator set *)
let is_isogram_recursive s =
  let lower = String.lowercase_ascii s in
  let module CS = Set.Make(Char) in
  let rec check i seen =
    if i >= String.length lower then true
    else
      let c = lower.[i] in
      if c >= 'a' && c <= 'z' then
        if CS.mem c seen then false
        else check (i + 1) (CS.add c seen)
      else check (i + 1) seen
  in
  check 0 CS.empty

let () =
  assert (is_isogram "lumberjacks");
  assert (not (is_isogram "eleven"));
  assert (is_isogram "");
  assert (is_isogram_recursive "subdermatoglyphic");
  assert (not (is_isogram_recursive "eleven"));
  Printf.printf "All isogram tests passed!\n"

📊 Detailed Comparison

Isogram Check — OCaml vs Rust Comparison

Core Insight

Duplicate detection is fundamentally a set membership problem. OCaml uses `List.sort_uniq` to compare lengths, while Rust's `HashSet::insert()` returns a boolean indicating whether the element was new — enabling early termination.

OCaml Approach

Filters characters to lowercase alpha, converts to list, applies `List.sort_uniq`, and compares lengths. The sort-based dedup is O(n log n). Alternatively, a recursive approach with `Set.Make(Char)` gives O(n log n) with early exit.

Rust Approach

Three approaches: (1) collect to Vec and HashSet, compare lengths — O(n) average; (2) early-exit using `HashSet::insert()` return value; (3) bitflag for zero-allocation O(n). The early-exit pattern is idiomatic Rust and has no direct OCaml equivalent without mutable state.

Comparison Table

Aspect	OCaml	Rust
Memory	List + sorted copy	HashSet or u32 bitflag
Null safety	N/A	N/A
Errors	Not applicable	Not applicable
Iteration	`Seq.filter` + `List.of_seq`	`.chars().filter().map()`
Dedup	`List.sort_uniq` (O(n log n))	`HashSet` (O(n) average)

Things Rust Learners Should Notice

1. `HashSet::insert()` returns bool — this is a key API design that enables early exit patterns 2. Three allocation tiers: HashSet (heap), Vec+HashSet (heap), bitflag u32 (stack-only) 3. `copied()` iterator adapter — converts `&char` to `char` for collecting into HashSet 4. Filtering and mapping are lazy — the iterator chain doesn't allocate until `collect()` 5. Rust's `return` in closures — early return only exits the closure, use a `for` loop for early function exit