Valid Anagram

Given two strings s and t, return True if t is an anagram of s.

TimeO(n)

SpaceO(1)

Given two strings s and t, return True if t is an anagram of s.

An anagram uses the exact same multiset of characters — same letters, same counts — possibly in a different order.

Constraints

Input: two lines — string s, then string t (read from stdin).
Output: print True or False on one line (once per approach in the reference solution).
Answer rule: True only when both strings have identical character frequencies.
Different lengths: if len(s) ≠ len(t), return False immediately.
Count-array approach: assumes lowercase English letters a–z.

Input

anagram
nagaram

Output

True

Explanation: Both strings use the same multiset of letters — a, a, a, g, m, n, r.

Naive Solution

Sort both strings and compare the results character by character.

If sorted(s) == sorted(t), both strings contain the same multiset of characters → anagram.

// Sort both strings; equal multisets have identical sorted forms.
// Time: O(n log n)  Space: O(n)
fn is_anagram_sort(s: &str, t: &str) -> bool {
    let mut s_sorted: Vec<char> = s.chars().collect();
    let mut t_sorted: Vec<char> = t.chars().collect();
    s_sorted.sort();
    t_sorted.sort();
    s_sorted == t_sorted
}

Time — O(n log n)

Sorting each string of length n dominates.

Space — O(n)

sorted() / to_vec() allocate copies of the character data.

Time: sorting is unnecessary when only counts matter, not order.

Space: two sorted copies are allocated.

Next step: count characters directly with hash maps — O(n) time, no sorting.

Two-Pass Solution

Guard: if len(s) ≠ len(t), return False.
Pass 1: build s_counter — a map from each character in s to its frequency.
Pass 2: build t_counter the same way for t.
Compare: for every (ch, count) in s_counter, check t_counter[ch] == count.

If all counts match, return True; otherwise False.

// Build a frequency map for each string, then compare counts per character.
// Time: O(n)  Space: O(n)
fn is_anagram_hash_map(s: &str, t: &str) -> bool {
    if s.len() != t.len() {
        return false;
    }
 
    let mut s_counter: HashMap<char, i32> = HashMap::new();
    let mut t_counter: HashMap<char, i32> = HashMap::new();
 
    for ch in s.chars() {
        *s_counter.entry(ch).or_insert(0) += 1;
    }
    for ch in t.chars() {
        *t_counter.entry(ch).or_insert(0) += 1;
    }
 
    for (ch, count) in s_counter {
        if t_counter.get(&ch).copied().unwrap_or(0) != count {
            return false;
        }
    }
    true
}

Time — O(n)

Two linear scans to build counters, plus O(k) comparison over distinct characters k ≤ n → O(n).

Space — O(n)

Two hash maps store up to k distinct characters each.

Tradeoff: linear time, but two maps and three passes (build s, build t, compare). Can we fold into one pass with fixed storage?

Optimal Solution

Use a fixed-size count array of length 26 (one slot per lowercase letter).

Walk both strings in lockstep at index i:

counter[ord(s[i]) - ord('a')] += 1
counter[ord(t[i]) - ord('a')] -= 1

After the scan, return True if every slot is 0 — each letter added from s was cancelled by t.

Guard first: if len(s) ≠ len(t), return False.

// Single pass: increment for s[i], decrement for t[i] in a 26-slot table.
// Time: O(n)  Space: O(1)
fn is_anagram_count_array(s: &str, t: &str) -> bool {
    if s.len() != t.len() {
        return false;
    }
 
    let s_chars: Vec<char> = s.chars().collect();
    let t_chars: Vec<char> = t.chars().collect();
    let mut counter: [i32; 26] = [0; 26];
 
    for idx in 0..s_chars.len() {
        counter[(s_chars[idx] as u8 - b'a') as usize] += 1;
        counter[(t_chars[idx] as u8 - b'a') as usize] -= 1;
    }
 
    counter.iter().all(|&c| c == 0)
}

Time — O(n)

Single pass over n characters with O(1) work per index → O(n).

Space — O(1)

The counter has fixed size 26 — does not grow with input length.

Result: same correctness as sort and hash map for lowercase inputs, with O(n) time and O(1) extra space.

Full source: Rust · Python