Livsy Code

LeetCode Blind 75: Valid Anagram

Greetings, traveler!

Another classic from the LeetCode Blind 75 list — Valid Anagram — is one of those simple problems that interviewers love because it tests how you think about data representation and time complexity trade-offs.
Let’s take a look at how to solve it cleanly in Swift.

Problem Overview

You’re given two strings, s and t.
Your task is to determine whether they are anagrams — meaning they contain the same letters with the same frequency, just possibly in a different order.

Constraints:

  • 1 <= s.length, t.length <= 5 * 104
  • s and t consist of lowercase English letters.

Follow up: What if the inputs contain Unicode characters? How would you adapt your solution to such a case?

Example 1

Input: s = "anagram", t = "nagaram"
Output: true

Example 2

Input: s = "rat", t = "car"
Output: false

1. The Simple Sorting Approach

The most straightforward way is to compare the sorted versions of both strings.
If they’re equal, the strings are anagrams.

func isAnagram(_ s: String, _ t: String) -> Bool {
		guard s.count == t.count else { return false }
    return s.sorted() == t.sorted()
}

How it works

Sorting rearranges the characters so that identical sets of characters line up in the same order.
After sorting, "anagram" and "nagaram" both become "aaagmnr", so they match.

Time/Space Complexity

  • Time complexity: Depends on the sorting algorithm, on average O(N log N).
  • Space complexity: O(1) or O(N) depending on the sorting algorithm.

2. Using a Dictionary (Counting Characters)

A more efficient solution counts how many times each character appears in s and t.

func isAnagram(_ s: String, _ t: String) -> Bool {
    guard s.count == t.count else { return false }
    
    var count: [Character: Int] = [:]
    
    for ch in s {
        count[ch, default: 0] += 1
    }
    for ch in t {
        count[ch, default: 0] -= 1
        if count[ch]! < 0 {
            return false
        }
    }
    return true
}

How it works

  1. We build a frequency table from the first string.
  2. Then, for every character in the second string, we subtract from the table.
  3. If any count ever becomes negative, it means t contains a letter not present (or overused) in s.

Complexity

  • Time: O(n)
  • Space: O(k) — proportional to the number of unique characters

This approach works with any Unicode characters, not just English letters.

3. Optimized Solution — Using an Array and ASCII Values

When we know the input is restricted to lowercase English letters (a–z),
we can replace the dictionary with a fixed-size array of 26 integers.
Each index represents one letter: 'a' maps to index 0, 'b' to 1, and so on.

func isAnagram(_ s: String, _ t: String) -> Bool {
    guard s.count == t.count else { return false }
    
    var count = Array(repeating: 0, count: 26)
    
    let aAscii = Character("a").asciiValue!
    
    for ch in s.utf8 {
        count[Int(ch - aAscii)] += 1
    }
    
    for ch in t.utf8 {
        count[Int(ch - aAscii)] -= 1
        if count[Int(ch - aAscii)] < 0 {
            return false
        }
    }
    
    return true
}

How it works

  • 'a' in ASCII equals 97, 'z' equals 122.
    Subtracting the value of 'a' gives us a zero-based index.
    For example, 'a' → 0, 'b' → 1, 'z' → 25.
  • For every letter in s, we increase its counter.
  • For every letter in t, we decrease it.
  • If any counter drops below zero, it means there are extra letters in t.
  • If all counters end up zero — the strings are perfect anagrams.

Complexity

  • Time complexity: O(N)
  • Space complexity: O(1) — (the array always has 26 elements)

It might be interesting: