Valid Anagram — Editorial

Opening the reading…

Intuitionwhy rearrangement is really a frequency comparison

Rearranging letters changes their positions but never changes how many times each letter appears. Therefore, t is an anagram of s exactly when both strings have the same count for every lowercase letter. The order of characters is irrelevant; the 26 frequencies are the complete information needed to decide the answer.

First add one to the count for every character in s. Then subtract one for every character in t. If a subtraction makes a count negative, t has already used some letter more times than s contains it, so the strings cannot match. If no count becomes negative and the lengths were equal, every count finishes at zero.

Approachone fixed-size counter and two passes

Compare the string lengths and return false when they differ, because an anagram must use every original letter exactly once and therefore must have the same number of letters.

Create an integer array of 26 zeroes, where position c - 'a' stores the balance for one lowercase letter; using the known alphabet avoids a map and keeps the storage fixed.

Scan s and increment the slot for each character, because these increments record how many copies of every letter are available.

Scan t and decrement the slot for each character, because each character in t consumes one available copy from s.

After each decrement, return false if that slot is negative, because t has requested a letter more times than s supplied it and later characters cannot repair that shortage.

Return true after the second scan, because equal lengths plus no negative balance means every letter count matches exactly.

Complexitythe alphabet keeps working memory fixed

MEASURE	BOUND	WHY
Time	O(n)	Each string is scanned once, and each character causes one array access and one arithmetic update. The two passes examine 2n characters, which is linear, and no character is revisited by another data structure.
Space	O(1) extra	The counter always contains exactly 26 integers, independent of n. The returned boolean is not working memory, and there is no output collection to count. The bound stays O(1) even for the largest or most uneven letter distributions because the alphabet size is fixed.

Here n denotes the common length of s and t after the length check; the alphabet has exactly 26 lowercase letters.

Annotated solutionC++ · two-pass frequency balance · the compact version

CPPCount each letter from s, consume those counts with t, and reject the first shortage.

#include <string>
#include <vector>

using namespace std;

class Solution {
public:
    bool isAnagram(string s, string t) {
        if (s.length() != t.length()) return false;

        vector<int> count(26, 0);
        for (char c : s) {
            count[c - 'a']++;
        }

        for (char c : t) {
            count[c - 'a']--;
            if (count[c - 'a'] < 0) return false;
        }

        return true;
    }
};

The early negative check is safe because counts begin with exactly the supply from s. Once one slot drops below zero, t has already used too many copies of that letter; the remaining characters cannot make that particular shortage disappear. The equal-length check then supplies the other half of the proof: without it, t could use fewer letters and still leave unused positive counts.

The sorting alternativesimpler comparison at the cost of extra time

A competent alternative is to sort both strings and compare the sorted results. Sorting removes the original order from both strings, so equal results mean the same letters appear with the same multiplicities. This is merely a different arrangement, not an optimisation: it uses O(n log n) time instead of O(n), while using O(n) additional storage for the copied or sorted string data.

CPPSort both strings and compare their canonical letter order.

#include <algorithm>
#include <string>

using namespace std;

class Solution {
public:
    bool isAnagram(string s, string t) {
        if (s.length() != t.length()) return false;

        sort(s.begin(), s.end());
        sort(t.begin(), t.end());
        return s == t;
    }
};