Check Whether Two Strings Are Anagrams

Quick Overview

Check whether two strings contain the same lowercase English letters with identical multiplicities, including empty and million-character inputs. Discuss case-sensitive contract boundaries, time and auxiliary-space expectations, Unicode generalization, inputs larger than memory, and grouping many words by anagram class.

Company: Databricks

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

## Problem Implement `are_anagrams(a, b)`. Return `true` exactly when `a` and `b` contain the same lowercase English letters with the same multiplicities, possibly in a different order. ## Constraints - `0 <= len(a), len(b) <= 1,000,000` - Both strings contain only characters `a` through `z`. - The empty string is an anagram of the empty string. ## Examples - `a = "listen"`, `b = "silent"` returns `true`. - `a = "rat"`, `b = "car"` returns `false`. - `a = "aab"`, `b = "abb"` returns `false`. ## Clarifications Do not ignore whitespace, punctuation, or case because those characters are excluded by the input contract. Aim for linear time and constant auxiliary space relative to input length. ## Hint Sorting works but does more work than necessary. A fixed-size frequency difference tracks exactly what must balance. ## Interview Follow-ups - Support arbitrary Unicode text. - Process inputs that do not fit in memory. - Group a large list of words into anagram classes.

Overview: Check whether two strings contain the same lowercase English letters with identical multiplicities, including empty and million-character inputs. Discuss case-sensitive contract boundaries, time and auxiliary-space expectations, Unicode generalization, inputs larger than memory, and grouping many words by anagram class.

Implement are_anagrams(a, b). Return true exactly when a and b contain the same lowercase English letters with the same multiplicities, possibly arranged in a different order. Both inputs contain only letters a through z, and two empty strings are anagrams.

Constraints

0 <= len(a), len(b) <= 1,000,000.
Both strings contain only lowercase English letters a through z.
The empty string is an anagram of the empty string.

Examples

Input: ('', '')

Expected Output: True

Explanation: Two empty strings have identical letter multiplicities.

Input: ('', 'a')

Expected Output: False

Explanation: Different lengths cannot have the same multiplicities.

Hints

Track the difference between the two strings' frequencies in one fixed-size array.

Approach

If the strings have different lengths, they cannot be anagrams. Otherwise, keep one frequency difference for each of the 26 allowed letters. Increment the matching counter for every character in a, then decrement it for every character in b. If a decrement makes a counter negative, b contains more copies of that letter than a and the answer is false. When all characters in two equal-length strings have been processed without a negative counter, every increment has a matching decrement, so all multiplicities are equal and the answer is true. The counter array always has 26 entries, independent of input length.

Time complexity:

O(len(a) + len(b))

Space complexity:

O(1)