---

The Complete Guide to Solving Anagrams in Cairo: From Logic to Code

Finding anagrams in Cairo involves normalizing input strings to a common format (e.g., lowercase), then comparing their character frequency maps using a Felt252Dict. A word is an anagram of a target if it has identical character counts, is not the same word, and shares the same length.

You stumble upon a vintage typewriter at a garage sale, a beautiful mechanical relic. Excited, you rush home, feed it a sheet of paper, and begin to type. But your excitement quickly fades as you inspect the output. The machine seems to have a mind of its own, printing "stop" when you typed "post," and "least" instead of "stale." It appears a random delay before each keypress is scrambling your words. You've just discovered a real-world anagram generator!

This quirky scenario perfectly captures the essence of the anagram problem, a classic challenge in computer science. It's not about broken typewriters, but about identifying words that contain the exact same letters, just in a different order. In this guide, we'll dissect this problem and build a robust solution using Cairo, the language powering the Starknet ecosystem. You'll learn not just the code, but the critical thinking and data structures required to write efficient, provable programs.

---

What Exactly is an Anagram?

Before we dive into Cairo code, we must establish a crystal-clear definition of our goal. An anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Let's break down the rules based on the classic definition from the exclusive kodikra.com curriculum:

• Same Letters, Same Count: The core principle. "listen" is an anagram of "silent" because both words contain one 'l', one 'i', one 's', one 't', one 'e', and one 'n'.
• Case-Insensitive: The comparison must ignore capitalization. "Listen" is still an anagram of "silent". For our program, this means we must normalize all input to a single case (e.g., lowercase) before comparing.
• Not The Same Word: A word is never its own anagram. "stop" is not an anagram of "stop", even though they share the same letters. This is a critical edge case to handle.
• Different Lengths are Impossible: If two words have a different number of letters, they can't possibly be anagrams. This provides a simple, highly efficient first check to filter out invalid candidates.

For example, given the target word "master", the word "stream" is a valid anagram. However, "team" is not (missing letters), and "streams" is not (extra letter).

---

Why is This a Foundational Skill in Cairo?

You might wonder, "Why solve a word puzzle in a language built for blockchain and zero-knowledge proofs?" The anagram problem is more than a simple puzzle; it's a vehicle for learning fundamental concepts that are absolutely critical for writing efficient and secure Starknet smart contracts.

Mastering this kodikra module teaches you:

• String Manipulation: Cairo handles strings as ByteArray objects. This problem forces you to iterate over them, process individual characters, and understand their underlying representation.
• Data Structures: The most efficient solution involves using a hash map to count character frequencies. In Cairo, this means mastering the Felt252Dict, a key-value store that is a cornerstone of many smart contracts.
• Algorithmic Thinking: You'll evaluate different strategies (like sorting vs. frequency counting) and understand their trade-offs, particularly in terms of computational cost (gas). This mindset is paramount in an environment where every operation has a real-world cost.
• Resource Management: Writing loops, allocating memory for dictionaries, and performing comparisons all consume computational resources. This exercise provides a practical, low-stakes environment to practice writing gas-efficient code.

Think of it as a workout for your brain. The "muscles" you build—handling data, designing algorithms, and optimizing for efficiency—are the same ones you'll need when building complex DeFi protocols or on-chain gaming systems.

---

How to Approach the Anagram Problem: The Algorithm

A robust algorithm solves a problem correctly and efficiently. For the anagram challenge, our strategy can be broken down into a clear, logical sequence. The most effective method is to use a "frequency map," which is a dictionary or hash map that stores each character and how many times it appears.

Here's the step-by-step logic:

Step 1: The Initial Filter

Before doing any complex work, we perform two quick checks on each candidate word against the target word:

1. Length Check: If candidate.len() != target.len(), it's impossible for them to be anagrams. We can immediately discard the candidate.
2. Identity Check: If the lowercase version of the candidate is identical to the lowercase version of the target, it's not an anagram by our rules. Discard it.

These checks are extremely cheap computationally and save us from wasting resources on obvious non-anagrams.

Step 2: Normalization

Since the comparison must be case-insensitive, we need a standard format. The simplest approach is to convert both the target word and the candidate word to all lowercase letters. This ensures that 'A' and 'a' are treated as the same character during our analysis.

Step 3: Building the Frequency Maps

This is the heart of the algorithm. We will create a frequency map for the (lowercase) target word. This map will have characters as keys and their counts as values.

For the target word "Listen" (which becomes "listen"):

• Iterate through each character: 'l', 'i', 's', 't', 'e', 'n'.
• For each character, update a Felt252Dict.
  • If the character is not in the dictionary, add it with a count of 1.
  • If it's already there, increment its count.

The resulting map for "listen" would look like this: { 'l': 1, 'i': 1, 's': 1, 't': 1, 'e': 1, 'n': 1 }.

Step 4: Comparing the Candidate

Now, for each candidate that passed the initial filter, we build its own frequency map in the same way. Once we have two maps—one for the target and one for the candidate—we simply compare them.

If the two frequency maps are identical (same keys with the same values), the words are anagrams!

Let's visualize this core logic with a diagram.

    ● Start with Target & Candidate
    │
    ▼
  ┌──────────────────┐
  │ Normalize both to │
  │    lowercase     │
  └────────┬─────────┘
           │
           ▼
  ┌──────────────────┐
  │ Build Frequency  │
  │ Map for Target   │ e.g., "rail" → {'r':1, 'a':1, 'i':1, 'l':1}
  └────────┬─────────┘
           │
           ▼
  ┌──────────────────┐
  │ Build Frequency  │
  │ Map for Candidate│ e.g., "liar" → {'l':1, 'i':1, 'a':1, 'r':1}
  └────────┬─────────┘
           │
           ▼
    ◆ Are the maps identical?
   ╱           ╲
  Yes           No
  ╱               ╲
 ▼                 ▼
Anagram!         Not an Anagram

---

Where is this Logic Implemented? The Cairo Code Walkthrough

Now let's translate our algorithm into working Cairo code. We'll structure our solution into helper functions to keep the code clean, readable, and easy to test. Our main function will be find_anagrams, which orchestrates the entire process.

The Core Utility: `build_char_map`

First, we need a reusable function to perform Step 3 of our algorithm: building a character frequency map. This function will take a ByteArray and return a Felt252Dict<u32>.

use core::dict::Felt252Dict;
use core::string::{ByteArray, try_string_into_felt252, felt252_into_string};

/// Builds a frequency map of characters for a given word.
/// Normalizes characters to lowercase.
fn build_char_map(word: @ByteArray) -> Felt252Dict<u32> {
    let mut char_map = Felt252Dict { };
    let mut i = 0;
    loop {
        if i >= word.len() {
            break;
        }

        // In Cairo, we often work with characters as short strings or felts.
        // We'll get a slice of the byte array for each character.
        let char_slice = word.slice(i, 1);
        
        // Convert to lowercase for case-insensitive comparison.
        let lower_char_slice = char_slice.to_lower();
        
        // Use try_string_into_felt252 for dictionary keys.
        let char_felt = try_string_into_felt252(@lower_char_slice).unwrap();

        // Update the map
        let current_count = char_map.get(char_felt);
        char_map.insert(char_felt, current_count + 1);
        
        i += 1;
    };
    char_map
}

Code Breakdown:

• use core::dict::Felt252Dict;: We import the necessary dictionary type from the Cairo core library.
• fn build_char_map(...): Defines our function, which takes a reference to a ByteArray (the @ signifies it's a snapshot) and returns a Felt252Dict.
• let mut char_map = Felt252Dict { };: We initialize an empty dictionary to store our character counts.
• loop { ... }: We use a standard loop to iterate over the bytes in the ByteArray.
• word.slice(i, 1): This extracts a single character (as a `ByteArray` of length 1) at the current index i.
• to_lower(): A crucial step for normalization. This converts the character slice to its lowercase equivalent.
• try_string_into_felt252(...): Dictionary keys in Cairo must be a felt252. This function converts our short string (the character) into a felt252. We use .unwrap() for simplicity, assuming a single ASCII character will always fit.
• char_map.get(char_felt): This retrieves the current count for the character. If the character isn't in the map, it returns the default value for u32, which is 0.
• char_map.insert(...): We insert the character back into the map with its count incremented by one.

The Main Logic: `find_anagrams`

This function ties everything together. It takes the target word and a list of candidates, then returns a new list containing only the valid anagrams.

/// Finds all anagrams for a given word from a list of candidates.
pub fn find_anagrams(target: @ByteArray, candidates: @Array<ByteArray>) -> Array<ByteArray> {
    let mut anagrams: Array<ByteArray> = array
![];

    // Normalize the target word and get its length once to avoid repeated work.
    let lower_target = target.to_lower()
;
    let target_len = target.len();
    
    // Build the frequency map for the target word once.
    let target_map = build_char_map(target);

    let mut i = 0;
    loop {
        if i >= candidates.len() {
            break;
        }

        let candidate = candidates.get(i).unwrap();
        let lower_candidate = candidate.to_lower();

        // --- Step 1: The Initial Filter ---
        // Check 1: Length must match.
        // Check 2: Must not be the same word.
        if candidate.len() == target_len && lower_candidate != lower_target {
            
            // --- Steps 3 & 4: Build and Compare Frequency Maps ---
            let candidate_map = build_char_map(candidate);

            if candidate_map == target_map {
                // It's a valid anagram, add it to our results.
                anagrams.append(candidate);
            }
        }
        
        i += 1;
    };

    anagrams
}

Code Breakdown:

• pub fn find_anagrams(...): A public function that takes the target word and an Array of candidates. It returns a new Array.
• let mut anagrams: Array<ByteArray> = array ![];: Initializes an empty array to store our results.
• let lower_target = target.to_lower() ;: We pre-process the target word by converting it to lowercase. This is an optimization to avoid doing it inside the loop.
• let target_map = build_char_map(target);: We also pre-calculate the target's frequency map. This is the most significant optimization, as it's done only once, not for every candidate.
• candidates.get(i).unwrap(): Inside the loop, we retrieve each candidate word.
• if candidate.len() == target_len && lower_candidate != lower_target: This is our efficient filter. It combines the length check and the identity check in a single condition.
• let candidate_map = build_char_map(candidate);: Only if a candidate passes the filter do we spend the resources to build its frequency map.
• if candidate_map == target_map: Cairo's Felt252Dict supports direct equality comparison. If the maps are identical, we've found an anagram.
• anagrams.append(candidate);: We add the original candidate word (preserving its case) to our results array.

This flow demonstrates a clean, efficient, and logical implementation of our anagram-finding algorithm in Cairo.

    ● Start `find_anagrams`
    │  (target, candidates)
    │
    ▼
  ┌───────────────────────┐
  │ Pre-process Target:   │
  │ - To Lowercase        │
  │ - Build Frequency Map │
  └──────────┬────────────┘
             │
             ▼
    ● Start Loop through `candidates`
    │
    ├─▶ For each `candidate`
    │   │
    │   ▼
    │ ◆ Pass Filter?
    │ │ (len == target_len &&
    │ │  lower(cand) != lower(target))
    │ ├─────────┐
    │ │ Yes     │ No
    │ │         └───────────┐
    │ ▼                     │
    │┌───────────────────┐  │
    ││ Build `cand_map`  │  │
    │└─────────┬─────────┘  │
    │          │            │
    │          ▼            │
    │    ◆ `cand_map` ==    │
    │      `target_map`?    │
    │    ╱             ╲    │
    │  Yes              No  │
    │   │               │   │
    │   ▼               │   │
    │ ┌───────────────┐ │   │
    │ │ Append to     │ │   │
    │ │ `anagrams` list │ │   │
    │ └───────────────┘ │   │
    │          │        │   │
    │          └────────┼───┘
    │                   │
    └───────────────────┘
             │
             ▼
    ● End Loop
    │
    ▼
  ┌───────────────────┐
  │ Return `anagrams` │
  └───────────────────┘

---

Performance Considerations & Risks

When writing code in any language, but especially in resource-aware environments like Starknet, it's vital to consider the trade-offs of your approach. The frequency map method is generally superior to another common method: sorting the letters of each string and comparing the results.

Here's a breakdown of the pros and cons in the context of Cairo:

Approach	Pros	Cons
Frequency Map (Felt252Dict)	Efficient Time Complexity: Generally linear time complexity (O(N), where N is the length of the string) for building the map. Idiomatic Cairo: Uses standard, well-optimized core library features like Felt252Dict.	Memory Overhead: Requires extra memory to store the dictionaries for the target and each candidate. In Cairo, this translates to higher gas costs for memory allocation.
Sorting Characters	Low Memory Overhead: Doesn't require an auxiliary data structure like a dictionary.	Higher Time Complexity: Sorting algorithms are typically O(N log N), which is less efficient than O(N) for large strings. Complex Implementation: String and array manipulation in Cairo can be more complex than in other languages. Implementing an efficient sorting algorithm for a ByteArray would require significant boilerplate code and could be gas-intensive.

Conclusion: For the vast majority of cases in Cairo, the Frequency Map approach is the clear winner. It's more straightforward to implement using the core library and is computationally more efficient, which directly translates to lower gas costs in a smart contract context.

---

Frequently Asked Questions (FAQ)

Why not just sort the strings to check for anagrams in Cairo?

While sorting is a valid algorithmic approach, it's less practical in Cairo. Implementing a character-sorting algorithm for Cairo's ByteArray is non-trivial and computationally more expensive (O(N log N)) than the linear time complexity (O(N)) of building a frequency map. The dictionary-based method is more idiomatic and gas-efficient for Cairo development.

What is a Felt252Dict and why is it used here?

A Felt252Dict is Cairo's built-in dictionary (or hash map) data structure. It stores key-value pairs, where the key must be a felt252. It's perfect for this problem because it provides a highly efficient way to count character occurrences. We convert each character to a felt252 to use it as a key, and the value stores its frequency (a u32 count).

How does Cairo handle strings and case-insensitivity?

Cairo represents strings using the ByteArray type, which is essentially an array of bytes. The core library provides utility functions for common string operations. For case-insensitivity, we use the .to_lower() method, which creates a new ByteArray with all ASCII alphabetic characters converted to their lowercase form. This normalization is a critical pre-processing step for our comparison.

Can this anagram-finding logic be used in a real Starknet smart contract?

Yes, absolutely. The logic and data structures (Felt252Dict, Array, ByteArray) are all part of the Cairo core library and are fully compatible with Starknet smart contracts. While finding anagrams might be a niche use case on-chain, the underlying skills—iterating, storing data in dictionaries, and managing resources—are directly applicable to building any kind of smart contract.

What are the main challenges when working with strings in Cairo?

The main challenges stem from Cairo's focus on provability and strong typing. String manipulation can feel more verbose than in languages like Python or JavaScript. Key challenges include converting between types (like ByteArray and felt252), the immutability of string data which often requires creating new `ByteArray` instances for modifications, and carefully managing memory and gas costs associated with these operations.

---

Conclusion: Beyond the Puzzle

We've successfully journeyed from a quirky typewriter story to a robust, efficient, and well-structured Cairo program for finding anagrams. By breaking the problem down, we designed an algorithm centered around normalization and frequency mapping—a powerful pattern for solving a wide range of computational problems. More importantly, we translated that logic into idiomatic Cairo code, leveraging the strengths of the Felt252Dict and optimizing our process to save computational resources.

This kodikra module is a testament to the idea that even simple puzzles can teach profound lessons. The principles of efficient data handling, algorithmic optimization, and resource management you've applied here are the bedrock of advanced blockchain development. Every loop, every dictionary insertion, and every comparison has prepared you for the greater challenges of building the decentralized future on Starknet.

Disclaimer: The code in this article is written for Cairo v2.x and the Starknet ecosystem. As the language and its libraries are under active development, syntax and function names may evolve. Always refer to the official documentation for the latest updates.

Ready to tackle the next challenge on your developer journey? Explore our complete Cairo learning path to continue building your skills, or get a broader perspective with our comprehensive Cairo language guide.

---

Published by Kodikra — Your trusted Cairo learning resource.