Quick Overview

Compare letter multiplicities case-insensitively to recognize anagrams, including repeated letters and empty strings.

Check Whether Two Words Are Case-Insensitive Anagrams

Company: Upstart

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Online Assessment

Determine whether two words are anagrams, ignoring letter case. Anagrams contain the same letters with the same multiplicities, possibly in a different order. ### Function Contract Implement `is_anagram(word_a, word_b) -> bool`. Return `true` exactly when the two case-insensitive letter multisets are equal. ### Constraints and Clarifications - Both arguments are defined strings and may be empty. - Each string has length at most 30. - Characters are uppercase or lowercase English letters only. - Repeated letters must occur equally often in both words. - Two empty strings are anagrams. ### Examples ```text word_a = "Drier" word_b = "Rider" Output: true ``` ```text word_a = "hello" word_b = "world" Output: false ``` ```hint Compare quantities, not just membership Knowing that both words contain the letter `a` does not reveal whether they contain it the same number of times. ```

Overview: Compare letter multiplicities case-insensitively to recognize anagrams, including repeated letters and empty strings.

Two words are anagrams when they contain exactly the same letters with the same multiplicities, possibly in a different order. Letter case is ignored, so 'A' and 'a' count as the same letter. Given two words `word_a` and `word_b`, implement `is_anagram(word_a, word_b) -> bool` that returns `True` exactly when the two case-insensitive letter multisets are equal, and `False` otherwise. Knowing only that both words contain some letter is not enough: a repeated letter must occur the same number of times in both words. Two empty strings are anagrams of each other. The return value is a boolean, so no numeric value crosses the function boundary. Examples Example 1: word_a = "Drier" word_b = "Rider" Output: True Both words reduce to the letter counts d:1, e:1, i:1, r:2 once case is ignored, so they are anagrams. Example 2: word_a = "hello" word_b = "world" Output: False The words have the same length but different letters, so the multisets are not equal. Constraints - Both `word_a` and `word_b` are defined strings and may be empty. - Each string has length at most 30. - Characters are uppercase or lowercase English letters (A-Z, a-z) only. - Repeated letters must occur equally often in both words. - Two empty strings are anagrams. Return a single boolean; there is no ordering or tie-breaking choice to make.

Constraints

  • Both word_a and word_b are defined strings and may be empty.
  • Each string has length at most 30.
  • Characters are uppercase or lowercase English letters (A-Z, a-z) only.
  • Repeated letters must occur equally often in both words.
  • Two empty strings are anagrams.
  • The return value is a boolean.

Examples

Input: ('', '')

Expected Output: True

Explanation: Minimum valid input: two empty strings hold the same (empty) letter multiset, so they are anagrams.

Input: ('', 'a')

Expected Output: False

Explanation: One word is empty and the other has a letter, so the multisets differ.

Hints

  1. Knowing that both words contain the letter 'a' does not reveal whether they contain it the same number of times: compare quantities, not just membership.
  2. Letter case must never change the answer, so decide early how you will make 'A' and 'a' indistinguishable before anything else compares them.
  3. There is a cheap property of the two words that must already agree before any letter comparison can succeed.

Loading coding console...

Show the approach

Approach

Two words are anagrams exactly when their case-folded letter multisets are equal. The reference builds the multiset of the first word as a counter keyed by the lowercased character, then consumes it with the second word.

Algorithm: (1) if the lengths differ the multisets cannot be equal, so return False immediately; (2) for each character of word_a, increment counts[lowercase(ch)]; (3) for each character of word_b, look up counts[lowercase(ch)] and return False if it is absent or already zero, otherwise decrement it; (4) return True.

Invariant: after processing the first k characters of word_b, counts holds exactly multiset(word_a) minus the multiset of those k consumed characters, and no entry has ever gone negative. Correctness: if the loop never returns False, every one of the n characters of word_b was matched against a distinct remaining occurrence in word_a; since the lengths are equal, all n occurrences of word_a are consumed and the residual counter is all zeros, which is exactly multiset equality. Conversely, if the multisets differ then either the lengths differ (caught in step 1) or some letter occurs more often in word_b than in word_a, and the first surplus occurrence of that letter finds a zero or missing count and returns False.

Case-insensitivity is handled by lowercasing each character before it is counted or looked up, so 'A' and 'a' are the same key on both sides. Edge cases: two empty strings skip both loops and return True; an empty word against a non-empty one is rejected by the length check; equal-length words that share a letter set but not its multiplicities (for example 'aab' vs 'abb') are rejected when the surplus letter finds a zero count. A comparison that only tested letter membership, or that compared characters case-sensitively, would be wrong on those inputs.

Time complexity:
O(n), where n is the length of the words (each character of each word is counted or consumed once)
Space complexity:
O(1), at most 26 counter entries regardless of input length