DSA-VerseLearn by watching code run
DashboardData StructuresAlgorithmsVisualizerCORECoding PlaygroundInterview QuestionsComplexity AnalyzerLearning NotesBookmarksLearning ProgressSettings
All interview questions

Interview preparation

Valid Anagram

EasyStringsHashingSorting and Searching
AmazonGoogleMicrosoft Community-reported practice tags — not verified company questions.

1Problem statement

Given two strings s and t of lowercase English letters, return true if t is an anagram of s (same letters with the same counts), otherwise false.

2Examples

Input: s = "anagram", t = "nagaram"
Output: true
Input: s = "rat", t = "car"
Output: false

3Constraints

  • 1 ≤ s.length, t.length ≤ 5 × 10⁴
  • s and t consist of lowercase English letters.

4Approaches

Approach 1

Brute Force

For every character of s, find and remove one matching character from t.

Time O(n²)Space O(n)

Approach 2

Better: Sort both

Sort both strings and compare.

Time O(n log n)Space O(n)

Approach 3

Optimal: Count letters

Increment counts for s, decrement for t in a 26-slot array; all counts must be zero.

Time O(n)Space O(1) (26 counters)

5Code (optimal approach)

Complete programs that print the example outputs — verified in JavaScript, Python, Java and Go.

function isAnagram(s, t) {
  if (s.length !== t.length) return false;
  const counts = new Array(26).fill(0);
  for (let i = 0; i < s.length; i++) {
    counts[s.charCodeAt(i) - 97]++;
    counts[t.charCodeAt(i) - 97]--;
  }
  return counts.every((c) => c === 0);
}

console.log(isAnagram("anagram", "nagaram"));
console.log(isAnagram("rat", "car"));

6Complexity

Time

O(n)

Space

O(1)

7Visual walkthrough

  1. 1.counts after "rat": r=1, a=1, t=1
  2. 2.after subtracting "car": c=−1, r=0, a=0, t=1
  3. 3.non-zero counts → not an anagram

8Related questions

Two Sum

On this page

  1. 01Problem statement
  2. 02Examples
  3. 03Constraints
  4. 04Approaches
  5. 05Code (4 languages)
  6. 06Complexity
  7. 07Visual walkthrough
  8. 08Related questions