Character Distribution Equivalence — Problem Statement & Solution Guide

BacktrackingMediumMixed

TimeO(n)

SpaceO(1) for fixed alphabet, O(k) for Unicode where k is distinct characters

Problem Description

Given two strings source and target, determine if they contain the same characters, where the frequency of each character in source must be equal to its frequency in target, without considering the order of characters.

DSA Pattern Breakdown

"Character Distribution Equivalence"

medium

WHY DOES IT MATTER?

Frequency‑based comparison is a fundamental pattern for any problem that asks whether two collections are permutations of each other, such as anagram detection, inventory reconciliation, or checksum validation. Mastering this pattern enables engineers to replace costly sorting or nested loops with linear scans, dramatically improving scalability.

OPTIMIZATION CHALLENGE

The breakthrough is realizing that order can be ignored, allowing us to replace sorting (O(n log n)) with a single pass frequency tally (O(n)). For bounded alphabets, the frequency array turns the problem into constant‑time updates, collapsing both time and space to linear and constant respectively.

REAL-WORLD CONNECTION

Think of a warehouse receiving two shipment manifests: the order of items on each manifest is irrelevant, only the quantity of each SKU matters. Verifying that both manifests match is analogous to checking character distribution equivalence in software.

During an interview, first ask clarifying questions about the character set; if it's limited, immediately propose a fixed‑size array. If not, fall back to a hash map. Always validate edge cases (empty strings, different lengths) before building the frequency map to short‑circuit the solution.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(1) for fixed alphabet, O(k) for Unicode where k is distinct characters

Core Theory — Why This Approach?

The problem reduces to checking multiset equality of two strings. A multiset (or bag) records the count of each distinct element, ignoring order, so two strings are equivalent if and only if their character frequency maps are identical. A naive solution that sorts both strings runs in O(n log n) time, which becomes a bottleneck for very large inputs (e.g., gigabyte‑scale logs) because the sorting overhead dominates and memory fragmentation can cause crashes. The optimal paradigm leverages a linear‑time counting technique: traverse each string once while updating a fixed‑size frequency array (or hash map for Unicode) and then compare the two structures. This yields O(n) time and O(1) auxiliary space for bounded alphabets, satisfying the constraints of high‑throughput systems.

When the character set is bounded (ASCII, lowercase English letters, etc.), a simple integer array of size 256 (or 26) can serve as the frequency counter, providing constant‑time updates. For unbounded Unicode, a hash map is used, still preserving O(n) expected time because each insertion/look‑up is amortized O(1). The key insight is that order does not matter; therefore, we can collapse the problem to a frequency comparison, eliminating the need for sorting or nested loops that would otherwise lead to O(n^2) or O(n log n) complexities.

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> in C++ or collections.Counter in Python) to store frequencies, because the character set size is no longer constant. The algorithm still runs in O(n) expected time, with O(k) space where k is the number of distinct characters encountered.

Q2Can you extend the algorithm to support streaming input where the target string is not fully available upfront?

Maintain a frequency counter for the source string, then as each character of the target stream arrives, decrement the corresponding count. If any count goes negative or the final counts are non‑zero after the stream ends, the strings are not equivalent. This uses O(1) additional space for bounded alphabets and processes the stream in a single pass.

Q3What is the time‑space trade‑off between using a fixed‑size array versus a hash map for frequency counting?

A fixed‑size array offers O(1) access and O(1) extra space when the alphabet size is known and small, but it wastes memory if the range is large. A hash map adapts to the actual distinct characters, using O(k) space where k ≤ n, and still provides amortized O(1) operations, at the cost of higher constant factors and potential collisions.

Examples

Example 1

Input

{"source":"abc","target":"cab"}

Output

true

Explanation: Step-by-step: We create two frequency maps for the source and target strings. We then compare the frequency maps to determine if they are equivalent. In this case, the frequency maps are equivalent, so we return true.

Example 2

Input

{"source":"abc","target":"abcd"}

Output

false

Constraints

1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9

Optimal Approach & Strategy

Build a frequency array (or hash map) for the first string, then decrement counts while scanning the second string; a single mismatch or leftover count indicates inequality. This runs in O(n) time with O(1) extra space for bounded alphabets.

Brute Force Approach

Sort both strings and then compare them character by character; this requires O(n log n) time due to the sorting step. Alternatively, nested loops that count each character against the other string would be O(n^2).

Verified Code Solutions

Language:

JavaScript Solution

Time: O(n)

function characterDistributionEquivalence(source, target) {
   if (source === null || target === null) {
      return false;
   }
   if (source.length === 0 || target.length === 0) {
      return false;
   }
   const sourceMap = new Map();
   const targetMap = new Map();
   for (let char of source) {
      sourceMap.set(char, (sourceMap.get(char) || 0) + 1);
   }
   for (let char of target) {
      targetMap.set(char, (targetMap.get(char) || 0) + 1);
   }
   if (sourceMap.size !== targetMap.size) {
      return false;
   }
   for (let [char, freq] of sourceMap) {
      if (targetMap.get(char) !== freq) {
         return false;
      }
   }
   return true;
}

class CharacterDistributionEquivalence {
public:
   bool characterDistributionEquivalence(string source, string target) {
      if (source.empty() || target.empty()) {
         return false;
      }
      unordered_map<char, int> sourceMap;
      unordered_map<char, int> targetMap;
      for (char c : source) {
         sourceMap[c]++;
      }
      for (char c : target) {
         targetMap[c]++;
      }
      if (sourceMap.size() != targetMap.size()) {
         return false;
      }
      for (auto& entry : sourceMap) {
         if (!targetMap.count(entry.first) || targetMap[entry.first] != entry.second) {
            return false;
         }
      }
      return true;
   }
};

public class CharacterDistributionEquivalence {
   public boolean characterDistributionEquivalence(String source, String target) {
      if (source == null || target == null) {
         return false;
      }
      if (source.length() == 0 || target.length() == 0) {
         return false;
      }
      Map<Character, Integer> sourceMap = new HashMap<>();
      Map<Character, Integer> targetMap = new HashMap<>();
      for (char c : source.toCharArray()) {
         sourceMap.put(c, sourceMap.getOrDefault(c, 0) + 1);
      }
      for (char c : target.toCharArray()) {
         targetMap.put(c, targetMap.getOrDefault(c, 0) + 1);
      }
      if (sourceMap.size() != targetMap.size()) {
         return false;
      }
      for (Map.Entry<Character, Integer> entry : sourceMap.entrySet()) {
         if (!targetMap.containsKey(entry.getKey()) || targetMap.get(entry.getKey()) != entry.getValue()) {
            return false;
         }
      }
      return true;
   }
}

def character_distribution_equivalence(source, target):
   if source is None or target is None:
      return False
   if len(source) == 0 or len(target) == 0:
      return False
   source_map = {}
   target_map = {}
   for char in source:
      source_map[char] = source_map.get(char, 0) + 1
   for char in target:
      target_map[char] = target_map.get(char, 0) + 1
   if len(source_map) != len(target_map):
      return False
   for char, freq in source_map.items():
      if target_map.get(char) != freq:
         return False
   return True

function characterDistributionEquivalence(source, target) {
   if (source === null || target === null) {
      return false;
   }
   if (source.length === 0 || target.length === 0) {
      return false;
   }
   const sourceMap = new Map();
   const targetMap = new Map();
   for (let char of source) {
      sourceMap.set(char, (sourceMap.get(char) || 0) + 1);
   }
   for (let char of target) {
      targetMap.set(char, (targetMap.get(char) || 0) + 1);
   }
   if (sourceMap.size !== targetMap.size) {
      return false;
   }
   for (let [char, freq] of sourceMap) {
      if (targetMap.get(char) !== freq) {
         return false;
      }
   }
   return true;
}

Asked in Top Tech Interviews

uncategorizedmediumgeneric

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.

Character Distribution Equivalence Solution

Problem Statement

Input

Output

Input

Output

Constraints

More Backtracking

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Character Distribution Equivalence — 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