Crack the Backend

Problem Statement

Given two strings s and t, return true if t is an anagram of s, and false otherwise. An anagram is a word or phrase formed by rearranging the letters of another (same characters with the same counts, possibly different order). Assume the strings contain only lowercase English letters (or clarify the character set).

If s and t have different lengths, they cannot be anagrams. We can count the frequency of each character in s, then decrement for each character in t; if all counts are zero, they are anagrams.

Key Observations

Frequency count: Use an array count[26] (or a map). For each character in s, count[c-'a']++. For each character in t, count[c-'a']--. If any count[i] != 0, return false; else return true. This is O(n) time and O(1) space (fixed 26).
Sorting: Sort both strings and compare. O(n log n) time. The count approach is preferred for O(n).

Approach

High-level: If s.length() != t.length() return false. Count chars in s (increment); count chars in t (decrement). If any count is non-zero, return false. Return true.

Steps:

if s.length() != t.length() return false. int[] count = new int[26].
For each c in s: count[c-'a']++. For each c in t: count[c-'a']--.
For each x in count: if x != 0 return false. return true.

Implementation

Java

public boolean isAnagram(String s, String t) {

    if (s.length() != t.length()) {
        return false;
    }

    int[] count = new int[26];

    for (char c : s.toCharArray()) {
        count[c - 'a']++;
    }

    for (char c : t.toCharArray()) {
        count[c - 'a']--;
    }

    for (int x : count) {
        if (x != 0) {
            return false;
        }
    }

    return true;
}

Test Cases

Example 1

Input

s = "anagram", t = "nagaram"

Expected

true

Explanation

Same chars and counts.

Complexity Analysis

Time: O(n).
Space: O(1) (26 letters).

Follow-ups

Group anagrams (hash by sorted string or count signature).