Anagram Verifier — Problem Statement & Solution Guide

StringsEasyFrequency Map

TimeO(n)

SpaceO(1)

Problem Description

Two strings are considered anagrams if they contain the exact same characters with the same frequencies, regardless of their order. Your task is to determine whether two given strings are anagrams of each other.

Given two strings s1 and s2, return true if s2 is an anagram of s1, and false otherwise. The comparison is case-sensitive, and only lowercase English letters are used in the input strings.

You may assume that both strings consist solely of lowercase alphabetic characters. The solution should efficiently verify the character frequency distribution of both strings to confirm their equivalence.

DSA Pattern Breakdown

"Anagram Verifier"

easy

WHY DOES IT MATTER?

Frequency‑counting is a core pattern for any problem that requires multiset equivalence, such as checking permutations, validating character constraints, or detecting duplicates efficiently.

OPTIMIZATION CHALLENGE

Recognizing that the alphabet size is constant lets you replace a generic hash map with a fixed‑size array, collapsing both time and space from O(n log n) or O(n)+O(k) to pure O(n)+O(1).

REAL-WORLD CONNECTION

Think of inventory management in a warehouse: each SKU’s count must match the order list; a single pass updating stock levels mirrors the increment‑decrement technique used for anagrams.

During an interview, write the increment‑decrement loop first, then add an early‑exit check for negative counts; this demonstrates both correctness and performance awareness.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(1)

Core Theory — Why This Approach?

An anagram check is fundamentally a frequency‑matching problem. The naive way of sorting both strings or comparing each character against every other leads to O(n log n) or O(n^2) time, which becomes costly for long inputs. By counting the occurrences of each character using a fixed‑size array (since only lowercase English letters are allowed) we can reduce the problem to a linear scan, guaranteeing O(n) time and O(1) extra space. This approach leverages the pigeon‑hole principle: with a known bounded alphabet, the frequency vector has constant size, so the algorithm scales directly with the length of the strings rather than the size of the alphabet.

The optimal paradigm falls under the category of “frequency counting” or “hash‑map counting”. When the character set is limited, an integer array of length 26 serves as a perfect hash, avoiding the overhead of a generic map. The algorithm increments counts for the first string and decrements for the second; a final pass confirming all zeros proves the strings are anagrams. This single‑pass technique eliminates the need for sorting or nested loops, making it both time‑optimal and space‑optimal for the given constraints.

Interview Questions on This Problem

Q1How would you modify the solution if the input could contain Unicode characters beyond lowercase English letters?

Use a hash map (e.g., unordered_map<char,int> or collections.Counter) to store frequencies because the alphabet size is no longer constant; the time remains O(n) but space becomes O(k) where k is the number of distinct characters.

Q2Can you solve the anagram verification in a single pass without extra storage?

Yes, by using a single integer array of size 26 and updating counts while iterating through both strings simultaneously: increment for s1[i] and decrement for s2[i]; if any count goes negative before the end, you can early‑return false.

Q3What is the time‑space trade‑off when you choose to sort both strings versus using a frequency array?

Sorting gives O(n log n) time and O(1) or O(n) space depending on the language, while frequency counting gives O(n) time and O(1) space for a fixed alphabet; the latter is preferred for large inputs and strict memory limits.

Examples

Example 1

Input

s1 = "listen", s2 = "silent"

Output

true

Explanation: Count the frequency of each character in s1: l:1, i:1, s:1, t:1, e:1, n:1. Count the frequency of each character in s2: s:1, i:1, l:1, e:1, n:1, t:1. Since the frequency maps are identical, the strings are anagrams.

Example 2

Input

s1 = "hello", s2 = "world"

Output

false

Explanation: Frequency map for s1: h:1, e:1, l:2, o:1. Frequency map for s2: w:1, o:1, r:1, l:1, d:1. The character 'h' appears in s1 but not in s2, and 'w', 'r', 'd' appear in s2 but not in s1. Thus, they are not anagrams.

Example 3

Input

s1 = "aab", s2 = "aba"

Output

true

Explanation: Frequency map for s1: a:2, b:1. Frequency map for s2: a:2, b:1. The frequency distributions match exactly, confirming that s2 is an anagram of s1.

Example 4

Input

s1 = "abc", s2 = "abcd"

Output

false

Explanation: The lengths of the strings differ (3 vs 4). Since anagrams must have the same length, the answer is immediately false without needing to compute full frequency maps.

Constraints

1 <= s1.length, s2.length <= 10^5
s1 and s2 consist of lowercase English letters only
The total number of test cases will not exceed 10^4

Optimal Approach & Strategy

Use a 26‑element count array, increment for s1 and decrement for s2 in a single pass, then verify all zeros – O(n) time, O(1) space.

Brute Force Approach

Sort both strings and compare them, or for each character in s1 scan s2 to count matches, leading to O(n log n) or O(n^2) time.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(n)

/**
 * Determines if s2 is an anagram of s1.
 * 
 * @param {string} s1 - The first string.
 * @param {string} s2 - The second string.
 * @return {boolean} - true if s2 is an anagram of s1, false otherwise.
 */
function isAnagram(s1, s2) {
    // If lengths differ, they cannot be anagrams
    if (s1.length !== s2.length) {
        return false;
    }
    
    // Frequency array for 26 lowercase letters
    const freq = new Array(26).fill(0);
    
    // Increment for s1, decrement for s2
    for (let i = 0; i < s1.length; i++) {
        freq[s1.charCodeAt(i) - 97]++;
        freq[s2.charCodeAt(i) - 97]--;
    }
    
    // Check if all frequencies are zero
    for (let count of freq) {
        if (count !== 0) {
            return false;
        }
    }
    
    return true;
}

// Driver code
function main() {
    const input = require('fs').readFileSync(0, 'utf8').trim().split(' ');
    const s1 = input[0];
    const s2 = input[1];
    
    const result = isAnagram(s1, s2);
    
    console.log(result ? 'true' : 'false');
}

main();

#include <iostream>
#include <string>
#include <vector>

using namespace std;

/**
 * Determines if s2 is an anagram of s1.
 * 
 * @param s1 The first string.
 * @param s2 The second string.
 * @return true if s2 is an anagram of s1, false otherwise.
 */
bool isAnagram(string s1, string s2) {
    // If lengths differ, they cannot be anagrams
    if (s1.length() != s2.length()) {
        return false;
    }
    
    // Frequency array for 26 lowercase letters
    vector<int> freq(26, 0);
    
    // Increment for s1, decrement for s2
    for (int i = 0; i < s1.length(); i++) {
        freq[s1[i] - 'a']++;
        freq[s2[i] - 'a']--;
    }
    
    // Check if all frequencies are zero
    for (int count : freq) {
        if (count != 0) {
            return false;
        }
    }
    
    return true;
}

int main() {
    string s1, s2;
    cin >> s1 >> s2;
    
    bool result = isAnagram(s1, s2);
    
    if (result) {
        cout << "true" << endl;
    } else {
        cout << "false" << endl;
    }
    
    return 0;
}

import java.util.Scanner;

public class Main {
    /**
     * Determines if s2 is an anagram of s1.
     * 
     * @param s1 The first string.
     * @param s2 The second string.
     * @return true if s2 is an anagram of s1, false otherwise.
     */
    public static boolean isAnagram(String s1, String s2) {
        // If lengths differ, they cannot be anagrams
        if (s1.length() != s2.length()) {
            return false;
        }
        
        // Frequency array for 26 lowercase letters
        int[] freq = new int[26];
        
        // Increment for s1, decrement for s2
        for (int i = 0; i < s1.length(); i++) {
            freq[s1.charAt(i) - 'a']++;
            freq[s2.charAt(i) - 'a']--;
        }
        
        // Check if all frequencies are zero
        for (int count : freq) {
            if (count != 0) {
                return false;
            }
        }
        
        return true;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s1 = scanner.next();
        String s2 = scanner.next();
        scanner.close();
        
        boolean result = isAnagram(s1, s2);
        
        System.out.println(result ? "true" : "false");
    }
}

def is_anagram(s1: str, s2: str) -> bool:
    """
    Determines if s2 is an anagram of s1.
    
    Args:
        s1: The first string.
        s2: The second string.
        
    Returns:
        True if s2 is an anagram of s1, False otherwise.
    """
    # If lengths differ, they cannot be anagrams
    if len(s1) != len(s2):
        return False
    
    # Frequency array for 26 lowercase letters
    freq = [0] * 26
    
    # Increment for s1, decrement for s2
    for c1, c2 in zip(s1, s2):
        freq[ord(c1) - ord('a')] += 1
        freq[ord(c2) - ord('a')] -= 1
    
    # Check if all frequencies are zero
    for count in freq:
        if count != 0:
            return False
    
    return True

if __name__ == "__main__":
    import sys
    input_data = sys.stdin.read().split()
    s1 = input_data[0]
    s2 = input_data[1]
    
    result = is_anagram(s1, s2)
    
    print("true" if result else "false")

/**
 * Determines if s2 is an anagram of s1.
 * 
 * @param {string} s1 - The first string.
 * @param {string} s2 - The second string.
 * @return {boolean} - true if s2 is an anagram of s1, false otherwise.
 */
function isAnagram(s1, s2) {
    // If lengths differ, they cannot be anagrams
    if (s1.length !== s2.length) {
        return false;
    }
    
    // Frequency array for 26 lowercase letters
    const freq = new Array(26).fill(0);
    
    // Increment for s1, decrement for s2
    for (let i = 0; i < s1.length; i++) {
        freq[s1.charCodeAt(i) - 97]++;
        freq[s2.charCodeAt(i) - 97]--;
    }
    
    // Check if all frequencies are zero
    for (let count of freq) {
        if (count !== 0) {
            return false;
        }
    }
    
    return true;
}

// Driver code
function main() {
    const input = require('fs').readFileSync(0, 'utf8').trim().split(' ');
    const s1 = input[0];
    const s2 = input[1];
    
    const result = isAnagram(s1, s2);
    
    console.log(result ? 'true' : 'false');
}

main();

Asked in Top Tech Interviews

Swiggy

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.

Anagram Verifier Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Input

Output

Constraints

More Strings

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Anagram Verifier — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Asked in Top Tech Interviews

Solve in Interative Editor