Valid Anagram - Practice Coding Problems

Valid Anagram - Problem

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 a different word or phrase, typically using all the original letters exactly once.

Input & Output

Example 1 — Basic Anagram

$ Input: s = "anagram", t = "nagaram"

› Output: true

💡 Note: Both strings contain exactly the same characters with the same frequencies: a(3), g(1), m(1), n(1), r(1). The letters are just rearranged.

Example 2 — Not an Anagram

$ Input: s = "rat", t = "car"

› Output: false

💡 Note: The strings have different characters: 'rat' has 't' but 'car' has 'c'. They cannot be anagrams of each other.

Example 3 — Different Lengths

$ Input: s = "listen", t = "silent"

› Output: true

💡 Note: Both strings have the same length and characters: e(1), i(1), l(1), n(1), s(1), t(1). They are perfect anagrams.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input

Two strings s and t to compare

Process

Count character frequencies or sort characters

Output

Return true if anagrams, false otherwise

Key Takeaway

🎯 Key Insight: Anagrams have identical character frequencies - count and compare to determine validity

Asked in

a Amazon 45 f Facebook 38 B Bloomberg 32 M Microsoft 28

The key insight is that anagrams have identical character frequency distributions. The optimal approach uses a single counter array to track character differences in O(n) time and O(1) space by incrementing for characters in s and decrementing for characters in t.

Common Approaches

Approach	Time	Space	Notes
✓ Single Pass Counter Array	O(n)	O(1)	Use a single counter array to track character differences
Brute Force - Sort Both Strings	O(n log n)	O(n)	Sort both strings and compare them character by character
Frequency Count with Hash Map	O(n)	O(1)	Count character frequencies in both strings and compare counts

Single Pass Counter Array — Algorithm Steps

Initialize frequency array for 26 lowercase letters
Iterate through both strings: increment for s[i], decrement for t[i]
Check if all frequency counts are zero

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Create counter array with all zeros

Process

For each position: +1 for s[i], -1 for t[i]

Verify

All counters should be zero if anagrams

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(char* s, char* t) {
    int sLen = strlen(s);
    int tLen = strlen(t);
    
    if (sLen != tLen) {
        return 0;
    }
    
    int count[26] = {0};
    
    for (int i = 0; i < sLen; i++) {
        count[s[i] - 'a']++;
        count[t[i] - 'a']--;
    }
    
    for (int i = 0; i < 26; i++) {
        if (count[i] != 0) {
            return 0;
        }
    }
    
    return 1;
}

int main() {
    char s[50001], t[50001];
    fgets(s, sizeof(s), stdin);
    fgets(t, sizeof(t), stdin);
    s[strcspn(s, "\n")] = 0;
    t[strcspn(t, "\n")] = 0;
    
    int result = solution(s, t);
    printf(result ? "true\n" : "false\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through both strings of length n

✓ Linear Growth

Space Complexity

O(1)

Fixed array of size 26 for lowercase letters is constant space

✓ Linear Space

321.3K Views

High Frequency

~15 min Avg. Time

8.5K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Single Pass Counter Array — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler