Rearrangement Equivalence Checker — Problem Statement & Solution Guide

StringsEasyFrequency Map

TimeO(n)

SpaceO(1)

Problem Description

Given two strings s and t, decide whether t can be formed by permuting the characters of s. No character may be added, removed, or altered; the two strings must contain exactly the same multiset of symbols. The first input line contains s, the second line contains t. Print "YES" if the multisets match, otherwise print "NO".

DSA Pattern Breakdown

"Rearrangement Equivalence Checker"

easy

WHY DOES IT MATTER?

Anagram checking is a fundamental pattern for any problem that requires multiset equivalence, appearing in security (signature verification), data deduplication, and compiler token analysis. Mastering this pattern builds a foundation for frequency‑based reasoning across algorithms.

OPTIMIZATION CHALLENGE

The key insight is that counting characters transforms a combinatorial comparison into a constant‑time lookup per character, collapsing O(n²) work into O(n) by exploiting the limited alphabet as a hash domain.

REAL-WORLD CONNECTION

Think of inventory reconciliation in a distributed warehouse: two shipment manifests must contain the exact same items in the same quantities. A frequency table acts like a ledger that quickly spots mismatches without scanning each item repeatedly.

When coding, first guard against length mismatch, then choose the simplest frequency container (array for lowercase letters, map otherwise) and perform a single pass that both increments and decrements counts – a single‑loop solution is both clean and fast.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(1)

Core Theory — Why This Approach?

The problem reduces to checking multiset equality of two strings, which is a classic instance of the anagram detection problem. A naive solution might compare every character of one string against every character of the other, leading to O(n²) time, which quickly becomes infeasible for large inputs (n up to 10⁵ or more). The optimal paradigm leverages counting – either via a fixed-size frequency array for bounded alphabets (e.g., ASCII) or a hash map for Unicode – to capture the exact number of occurrences of each character in linear time. By incrementing counts for the first string and decrementing for the second, we can verify equality with a single pass, guaranteeing O(n) time and O(1) or O(k) auxiliary space where k is the alphabet size.

Interview Questions on This Problem

Q1How would you modify the solution if the strings could contain Unicode characters beyond the ASCII range?

Use a hash map (e.g., unordered_map<char32_t,int>) to store frequencies because the alphabet size is no longer constant, still achieving O(n) time with O(k) space where k is the number of distinct characters present.

Q2Can you solve the problem without extra space while still running in linear time?

Yes, by sorting both strings in-place (O(n log n) time) and then scanning them simultaneously, but this trades space for time; true O(1) extra space with O(n) time is only possible when the alphabet size is bounded.

Q3What edge case should you watch for when the input strings have different lengths?

If lengths differ, the answer is immediately "NO" because a permutation cannot change string length; checking length first avoids unnecessary work.

Examples

Example 1

Input

listen
silent

Output

YES

Explanation: Both strings contain one each of the letters a, e, i, l, n, s, t. Since the character counts are identical, t is a permutation of s.

Example 2

Input

algorithm
logarithm

Output

YES

Explanation: The letters of "algorithm" are a,g,i,l,m,o,r,t,h. "logarithm" contains exactly the same letters with the same frequencies, so the strings are rearrangements of each other.

Example 3

Input

hello
world

Output

NO

Explanation: "hello" has two 'l's and no 'w', 'r', or 'd', while "world" contains 'w','r','d' and only one 'l'. The character multisets differ, therefore t cannot be obtained by rearranging s.

Constraints

1 <= |s|, |t| <= 100000
s and t consist of printable ASCII characters (code 32 to 126)
The total length of input does not exceed 200000 characters

Optimal Approach & Strategy

Build a frequency table for one string and verify the second string against it, achieving O(n) time and O(1) extra space for fixed alphabets.

Brute Force Approach

Compare each character of the first string with every character of the second, marking used characters, which leads to O(n²) time.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(n)

const fs = require('fs');
const input = fs.readFileSync(0, 'utf8').split(/\n/);
function areAnagrams(s, t) {
    if (s.length !== t.length) return false;
    const cnt = new Array(256).fill(0);
    for (let i = 0; i < s.length; i++) cnt[s.charCodeAt(i)]++;
    for (let i = 0; i < t.length; i++) {
        if (--cnt[t.charCodeAt(i)] < 0) return false;
    }
    return true;
}
const s = input[0] || '';
const t = input[1] || '';
process.stdout.write(areAnagrams(s, t) ? 'YES' : 'NO');

#include <bits/stdc++.h>
using namespace std;

bool areAnagrams(const string& s, const string& t) {
    if (s.size() != t.size()) return false;
    vector<int> cnt(256, 0);
    for (unsigned char c : s) cnt[c]++;
    for (unsigned char c : t) {
        if (--cnt[c] < 0) return false;
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s, t;
    getline(cin, s);
    getline(cin, t);
    cout << (areAnagrams(s, t) ? "YES" : "NO");
    return 0;
}

import java.io.*;
import java.util.*;

public class Main {
    static boolean areAnagrams(String s, String t) {
        if (s.length() != t.length()) return false;
        int[] cnt = new int[256];
        for (int i = 0; i < s.length(); i++) {
            cnt[s.charAt(i)]++;
        }
        for (int i = 0; i < t.length(); i++) {
            if (--cnt[t.charAt(i)] < 0) return false;
        }
        return true;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        String t = br.readLine();
        if (s == null) s = "";
        if (t == null) t = "";
        System.out.print(areAnagrams(s, t) ? "YES" : "NO");
    }
}

import sys

def are_anagrams(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False
    cnt = [0] * 256
    for ch in s:
        cnt[ord(ch)] += 1
    for ch in t:
        idx = ord(ch)
        cnt[idx] -= 1
        if cnt[idx] < 0:
            return False
    return True

def main():
    data = sys.stdin.read().splitlines()
    s = data[0] if len(data) > 0 else ''
    t = data[1] if len(data) > 1 else ''
    print('YES' if are_anagrams(s, t) else 'NO')

if __name__ == "__main__":
    main()

const fs = require('fs');
const input = fs.readFileSync(0, 'utf8').split(/\n/);
function areAnagrams(s, t) {
    if (s.length !== t.length) return false;
    const cnt = new Array(256).fill(0);
    for (let i = 0; i < s.length; i++) cnt[s.charCodeAt(i)]++;
    for (let i = 0; i < t.length; i++) {
        if (--cnt[t.charCodeAt(i)] < 0) return false;
    }
    return true;
}
const s = input[0] || '';
const t = input[1] || '';
process.stdout.write(areAnagrams(s, t) ? 'YES' : 'NO');

Asked in Top Tech Interviews

TCS

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.

Rearrangement Equivalence Checker Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Constraints

More Strings

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Rearrangement Equivalence Checker — 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