Isogram in Common-lisp: Complete Solution & Deep Dive Guide

a close up of a computer screen with code on it

Learn Isogram Detection in Common Lisp from Zero to Hero

An isogram is a word or phrase that contains no repeating letters, though characters like spaces and hyphens can appear multiple times. In Common Lisp, determining if a string is an isogram involves filtering non-alphabetic characters, normalizing the case, and then efficiently checking for duplicates using data structures like a hash table.

The Curious Case of the Non-Pattern Word

Imagine you're building a word game, a data validation system, or simply tackling a coding challenge. You encounter a peculiar requirement: verify if a word has any repeating letters. It sounds straightforward, but as you dig deeper, you realize the elegance of the solution reveals a lot about your chosen programming language's strengths.

This exact problem, identifying an "isogram," is a classic computer science puzzle. It's a fantastic exercise not just in logic, but in mastering fundamental data manipulation techniques. In a language as powerful and expressive as Common Lisp, this challenge becomes an opportunity to explore its rich standard library and functional programming paradigms. This guide will walk you through the entire process, from understanding the core concept to implementing a robust and efficient solution.

What Exactly is an Isogram?

Before we dive into the code, let's solidify our understanding of the problem. The definition is simple but has important nuances that will directly influence our algorithm.

An isogram is a word or phrase where no alphabetic character appears more than once. The key constraints from the kodikra learning path module are:

No Repeating Letters: The core rule. The letter 'a' can only appear once, 'b' only once, and so on.
Case-Insensitive: The letters 'A' and 'a' are considered the same. Our logic must treat them as identical to correctly identify duplicates.
Spaces and Hyphens are Ignored: These characters are allowed to repeat and should not be considered when checking for duplicate letters. For example, "six-year-old" is a valid isogram.

Let's look at some examples to make it crystal clear:

lumberjacks - Is an isogram. Every letter is unique.
background - Is an isogram.
six-year-old - Is an isogram. The hyphens are ignored, and all letters (s, i, x, y, e, a, r, o, l, d) are unique.
isograms - Is not an isogram because the letter 's' appears twice.
Common Lisp - Is not an isogram. The 'o' and 'm' repeat.

Our goal is to write a function that takes any string as input and returns true if it meets these criteria and false otherwise.

Why is Solving This Problem Important?

While "isogram checker" might not be a feature you ship daily, the underlying principles are fundamental to software development. Mastering this problem in Common Lisp strengthens your skills in several key areas:

Algorithmic Thinking: You learn to break down a problem into smaller, manageable steps: filtering, normalization, and duplicate detection. This is the heart of programming.
Data Structures: This problem is a perfect showcase for understanding the trade-offs between different data structures. We'll explore solutions using hash tables and sorted lists, highlighting their performance characteristics (Time and Space Complexity).
String and Sequence Manipulation: You'll gain hands-on experience with essential Common Lisp functions for handling strings, characters, and sequences, like loop, remove-if-not, and alpha-char-p.
Functional Concepts: Lisp encourages a functional style. We'll see how to process data through a pipeline of transformations, a common pattern in modern software development.
Technical Interviews: Variations of this problem ("find the first non-repeating character," "check for anagrams") are extremely common in technical interviews. A solid understanding here prepares you for real-world hiring scenarios.

Essentially, this exercise from the kodikra.com curriculum is a microcosm of larger, more complex data processing tasks you'll face in your career.

How to Implement an Isogram Checker in Common Lisp

Our strategy will follow a clear, three-step process. This logical pipeline makes the code easy to read, debug, and maintain.

Filter: Isolate only the relevant characters. We need to strip out spaces, hyphens, and any other non-alphabetic symbols.
Normalize: Convert all characters to a consistent case (e.g., all lowercase) to ensure 'A' and 'a' are treated as the same character.
Detect Duplicates: Iterate through the cleaned-up string and check if any character has been seen before. A hash table is the most efficient tool for this job.

Let's visualize this logic flow before writing the code.

    ● Start: Input Phrase
    │
    ▼
  ┌───────────────────┐
  │  Filter Characters  │
  │ (keep only letters) │
  └─────────┬─────────┘
            │
            ▼
  ┌───────────────────┐
  │ Normalize Case    │
  │ (e.g., to lowercase)│
  └─────────┬─────────┘
            │
            ▼
    ◆ Loop through each character
   ╱              ╲
  Is it in         Add to
  seen set?         seen set
  ╱    ╲             │
Yes     No           │
 │       ╲          ╱
 ▼        ▼        ╱
[Return False]  Continue Loop
 │
 └─────────────────► ● End: Return True (if loop completes)

The Primary Solution: Using a Hash Table

A hash table (or dictionary/map in other languages) provides constant time, O(1), average lookups. This makes it incredibly efficient for keeping track of the characters we've already encountered.

Here is a complete, idiomatic Common Lisp solution using this approach.


;;; This solution is part of the exclusive kodikra.com curriculum.

(defun isogram-p (phrase)
  "Determines if a word or phrase is an isogram.
   An isogram is a word with no repeating letters, ignoring case,
   spaces, and hyphens."
  (let ((seen-chars (make-hash-table :test 'eql)))
    ;; The LOOP macro is powerful for complex iterations.
    ;; We iterate over each character in the input phrase.
    (loop for char across (string-downcase phrase)
          
          ;; We only care about alphabetic characters.
          when (alpha-char-p char)
            
            ;; gethash returns two values: the value (or nil) and a boolean
            ;; indicating if the key was found. We only need the boolean here.
            do (if (gethash char seen-chars)
                   ;; If the character is already in our hash table,
                   ;; we've found a duplicate. Return NIL immediately.
                   (return-from isogram-p nil)
                   
                   ;; Otherwise, add the character to the hash table.
                   ;; The value can be anything, T is conventional.
                   (setf (gethash char seen-chars) t)))
    
    ;; If the loop completes without finding any duplicates,
    ;; the phrase is an isogram. Return T.
    t))

Step-by-Step Code Walkthrough

Let's dissect this function piece by piece to understand how it perfectly executes our strategy.

Function Definition:
```
(defun isogram-p (phrase) ... )
```
We define a function named isogram-p that accepts one argument, phrase. The -p suffix is a common Lisp convention for predicates—functions that return a boolean-like value (T for true, NIL for false).
Creating the Hash Table:
```
(let ((seen-chars (make-hash-table :test 'eql))) ... )
```
We use let to create a local variable seen-chars. We initialize it as a new hash table using make-hash-table. The :test 'eql' argument is crucial; it tells the hash table to compare keys (our characters) by identity for numbers and characters, and by address for other objects. This is the correct and efficient test for characters.
The Mighty loop Macro:
```
(loop for char across (string-downcase phrase) ... )
```
This is the engine of our function. First, (string-downcase phrase) handles our Normalization step. It returns a new string with all characters converted to lowercase. The loop macro then iterates over this new string, binding each character to the variable char on each pass.
Filtering Logic:
```
when (alpha-char-p char) ...
```
Inside the loop, we use when (a conditional that only executes its body if the condition is true). The condition (alpha-char-p char) checks if the current character is a letter of the alphabet. This elegantly handles our Filtering step, ignoring spaces, hyphens, numbers, and punctuation.
Duplicate Detection:
```
do (if (gethash char seen-chars)
           (return-from isogram-p nil)
           (setf (gethash char seen-chars) t))
```
This is the core logic. (gethash char seen-chars) attempts to find the character char in our hash table. If it's found, it means we've seen this letter before. The if condition becomes true, and we immediately exit the entire function, returning nil with (return-from isogram-p nil). This is called an early exit, and it's very efficient.

If gethash does not find the character, we execute the `else` part: (setf (gethash char seen-chars) t). This adds the new character to our hash table, so we can detect it if it appears again later.
The Success Case:
```
t
```
The final t at the end of the function is the default return value. If the loop finishes without ever hitting the (return-from isogram-p nil), it means no duplicates were found. The function then proceeds to its last expression, which is t, signaling that the phrase is indeed an isogram.

Testing the Solution in a REPL

You can test this function in any Common Lisp environment (like SBCL or CLISP). Save the code to a file (e.g., isogram.lisp) and load it.


$ sbcl
* (load "isogram.lisp")
T
* (isogram-p "lumberjacks")
T
* (isogram-p "background")
T
* (isogram-p "six-year-old")
T
* (isogram-p "isograms")
NIL
* (isogram-p "Hello World")
NIL

The output confirms our logic works as expected for all test cases.

Alternative Approach: Sorting the String

While the hash table approach is arguably the most efficient in terms of time complexity, it's not the only way to solve the problem. Another common technique involves sorting the characters and then checking for adjacent duplicates.

The logic for this approach is:

Filter out non-alphabetic characters and normalize to lowercase, just like before.
Sort the resulting sequence of characters.
Iterate through the sorted sequence and check if any character is the same as the one immediately following it.

Visualizing the Sorting Logic

    ● Start: Input Phrase
    │
    ▼
  ┌───────────────────┐
  │  Filter & Normalize │
  │ (letters, lowercase)│
  └─────────┬─────────┘
            │
            ▼
  ┌───────────────────┐
  │   Sort Characters   │
  │   (e.g., "aba" → "aab") │
  └─────────┬─────────┘
            │
            ▼
    ◆ Loop: Compare char[i] with char[i+1]
   ╱              ╲
  Are they          Continue
  the same?          Loop
  ╱    ╲
Yes     No
 │       ╲
 ▼        ▼
[Return False]  ● End: Return True (if loop completes)

Implementation with Sorting

Here's how you could write this in Common Lisp:


;;; An alternative solution from the kodikra.com curriculum.

(defun isogram-p-sorted (phrase)
  "Determines if a word is an isogram using a sorting approach."
  ;; Step 1: Filter and Normalize
  (let ((cleaned-chars (remove-if-not #'alpha-char-p (string-downcase phrase))))
    
    ;; Step 2: Sort the sequence of characters
    (let ((sorted-chars (sort cleaned-chars #'char<)))
      
      ;; Step 3: Check for adjacent duplicates
      ;; The 'loop' macro can iterate with two variables at once.
      (loop for c1 across sorted-chars
            for c2 across (subseq sorted-chars 1)
            
            ;; If any adjacent characters are the same, it's not an isogram.
            when (char= c1 c2)
              do (return-from isogram-p-sorted nil))
      
      ;; If the loop finishes, no adjacent duplicates were found.
      t)))

Pros and Cons: Hash Table vs. Sorting

Choosing the right algorithm often involves trade-offs. Let's compare our two solutions. This is a critical skill for any developer.

Metric	Hash Table Approach	Sorting Approach
Time Complexity	O(n) - We iterate through the string of length 'n' once. Hash table lookups and insertions are O(1) on average.	O(n log n) - The dominant operation is sorting the string, which is typically O(n log n). The final scan is O(n).
Space Complexity	O(k) - Where 'k' is the number of unique characters (at most 26 for the English alphabet). This is effectively O(1) or constant space.	O(n) or O(log n) - Depending on the sort implementation. A new sorted string of length 'n' is often created, so it's typically O(n).
Readability	Highly readable. The logic directly maps to the idea of "have I seen this before?".	Also quite readable, but the intent ("sort to find duplicates") is slightly less direct than the hash table's intent.
When to Use	Generally the preferred method for this problem due to its superior time efficiency. Ideal for large inputs.	A perfectly valid solution, especially if memory usage is extremely constrained and modifying the input array in-place is an option (though our Lisp example creates a new copy).

For most practical applications, the Hash Table solution is superior due to its linear time complexity.

Frequently Asked Questions (FAQ)

What is the time complexity of the primary hash table solution?

The time complexity is O(n), where 'n' is the length of the input phrase. This is because we perform a single pass over the string. Each operation inside the loop—checking for an alphabet character, looking up in the hash table, and inserting into the hash table—takes, on average, constant time, O(1). Therefore, the total time is directly proportional to the length of the string.

Why is it important to ignore character case?

The problem definition requires that 'a' and 'A' be treated as the same letter. If we didn't normalize the case (e.g., by using string-downcase), a word like "Programming" would be incorrectly identified as an isogram because 'P' and 'p' would be considered different characters by the computer.

Can this solution handle Unicode characters?

Yes, Common Lisp has excellent Unicode support. The functions string-downcase, alpha-char-p, and character comparisons work correctly with a wide range of Unicode characters. The hash table will also handle them without issue. For example, a string like "français" would correctly identify the 'ç' as a unique alphabetic character.

Is a recursive solution a good idea for this problem?

While you could write a recursive solution, it's generally not the most idiomatic or efficient approach in Common Lisp for this specific problem. An iterative solution using the loop macro is clearer, more performant, and avoids potential stack overflow issues with very long strings. Tail-call optimization could mitigate the stack issue, but the iterative form remains more natural here.

How would I test this function using a testing framework?

In the Common Lisp ecosystem, you might use a library like FiveAM or Parachute. A simple test case using a hypothetical (is ...) macro from a testing framework would look like this:


(is (isogram-p "dermatoglyphics") "a long isogram")
(is (not (isogram-p "isogram")) "a non-isogram with a repeating 's'")
(is (isogram-p "thumbscrew-japingly") "isogram with a hyphen")
(is (isogram-p "six-year-old") "isogram with a hyphen and spaces")

What are other similar word puzzles I can solve to practice?

Great question! If you enjoyed this, you should try solving problems like Anagram Detection (checking if two words use the same letters), Palindrome Checking (checking if a word reads the same forwards and backward), and finding the first non-repeating character in a string. These all build on the same fundamental skills of string manipulation and data structure usage.

Conclusion: More Than Just a Word Game

We've successfully dissected the isogram problem, transforming a simple definition into a robust, efficient, and idiomatic Common Lisp solution. Along the way, we explored fundamental concepts: algorithmic decomposition, the power of hash tables for tracking state, the elegance of the loop macro, and the importance of analyzing performance trade-offs with an alternative sorting-based approach.

This challenge, featured in the kodikra Common Lisp learning curriculum, is a perfect example of how a small problem can be a gateway to mastering a language's core features. The skills you've reinforced here—data filtering, normalization, and efficient duplicate detection—are universally applicable in countless real-world programming scenarios.

Disclaimer: All code examples are written for modern Common Lisp implementations like SBCL 2.4+ and should be compatible with the ANSI Common Lisp standard.

Ready for your next challenge? Explore our complete Common Lisp learning roadmap to continue building your skills.

Published by Kodikra — Your trusted Common-lisp learning resource.

kodikra

Search this blog