Fascinating Frequency String — Problem Statement & Solution Guide
Problem Description
You are given a string s composed exclusively of lowercase English letters. Your task is to verify whether the frequency distribution of the characters in the string is strictly unique. Specifically, for every distinct character present in s, the count of its occurrences must be different from the count of any other distinct character in the string.
If two or more distinct characters share the same occurrence count, the string is considered to have a non-unique frequency profile. Return true if all distinct characters have distinct occurrence counts, and false otherwise.
For example, if the string contains 'a' three times and 'b' three times, the condition is violated because both characters have a frequency of 3. However, if 'a' appears 3 times and 'b' appears 5 times, the condition holds for these two characters.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Fascinating Frequency String"
WHY DOES IT MATTER?
Detecting duplicate frequencies is a classic example of the "unique elements" pattern, which appears in many validation and data‑integrity checks. Mastering this pattern helps candidates quickly reason about constraints that involve distinctness across aggregated values.
OPTIMIZATION CHALLENGE
The key insight is to separate counting from uniqueness verification and to use a hash set (or bitmask) to capture duplicates in O(1) average time per frequency, turning a potentially quadratic comparison into a linear scan.
REAL-WORLD CONNECTION
In distributed logging systems, each service may emit a count of error types; ensuring that no two services report the same error count can be used to detect misconfiguration or duplicate reporting, mirroring the uniqueness‑of‑frequency check.
During an interview, first write the frequency counting loop, then immediately think "how do I know if a count was seen before?" – a set or boolean array is your go‑to tool. Keep the code short and avoid premature micro‑optimizations.
COMPLEXITY AT A GLANCE
O(n)O(1)Core Theory — Why This Approach?
The problem reduces to checking whether the multiset of character frequencies in a string contains any duplicates. A naive solution would compare each pair of characters, leading to O(k^2) time where k is the number of distinct letters (up to 26). However, because the alphabet size is constant, we can achieve linear time by counting frequencies in a single pass and then verifying uniqueness using a hash set. This approach leverages the pigeonhole principle: if two characters share the same count, the set will detect a collision when we attempt to insert the second occurrence.
The optimal paradigm is a two‑step linear scan: first, build a frequency array of size 26 (or a hash map for arbitrary alphabets). Second, iterate over the non‑zero frequencies and insert each into a hash set; if insertion fails because the value already exists, the string fails the uniqueness test. This eliminates the need for nested loops and keeps both time and auxiliary space proportional to the alphabet size, which is O(1) for lowercase English letters but scales gracefully for larger character sets.
Interview Questions on This Problem
Q1How would you modify the solution if the input string could contain Unicode characters beyond the English alphabet?
Replace the fixed-size 26‑element array with a hash map (e.g., unordered_map<char,int>) to count frequencies. The rest of the algorithm stays the same: iterate over the map’s values and use a hash set to detect duplicate frequencies. Time remains O(n) and space becomes O(u) where u is the number of unique characters.
Q2Can you solve the problem in O(1) additional space without using a hash set?
Yes. After counting frequencies, sort the non‑zero counts (using counting sort because the maximum frequency is bounded by n) and then scan for adjacent equal values. Sorting the limited range of counts uses O(1) extra space beyond the input array.
Q3Why is it safe to assume O(1) space for the frequency array when the string length can be up to 10^5?
The space depends on the size of the character set, not the string length. For lowercase English letters the alphabet size is fixed at 26, so the frequency array occupies constant space regardless of n, satisfying O(1) auxiliary space.
Examples
Input
s = "abac"
Output
false
Explanation: Step 1: Count the occurrences of each character. 'a' appears 2 times, 'b' appears 1 time, and 'c' appears 1 time. Step 2: List the frequencies: [2, 1, 1]. Step 3: Check for uniqueness. The frequency 1 appears twice (for 'b' and 'c'). Step 4: Since there is a duplicate frequency, return false.
Input
s = "abcabcabc"
Output
false
Explanation: Step 1: Count the occurrences. 'a' appears 3 times, 'b' appears 3 times, and 'c' appears 3 times. Step 2: List the frequencies: [3, 3, 3]. Step 3: Check for uniqueness. All frequencies are identical. Step 4: Since the frequencies are not distinct, return false.
Input
s = "aabbccddeeffgghhiijjkkllmmnnooppqqrrssttuuvvwwxxyyzz"
Output
false
Explanation: Step 1: Count the occurrences. Each letter from 'a' to 'z' appears exactly 2 times. Step 2: List the frequencies: [2, 2, ..., 2] (26 times). Step 3: Check for uniqueness. All frequencies are the same. Step 4: Return false.
Input
s = "aabbbcccccc"
Output
true
Explanation: Step 1: Count the occurrences. 'a' appears 2 times, 'b' appears 3 times, and 'c' appears 6 times. Step 2: List the frequencies: [2, 3, 6]. Step 3: Check for uniqueness. All values in the list are distinct. Step 4: Return true.
Constraints
- 1 <= s.length <= 100
- s consists of lowercase English letters only.
Optimal Approach & Strategy
Use a single pass to build a frequency map, then insert each non‑zero frequency into a hash set; a duplicate insertion signals a conflict, achieving O(n) time.
Brute Force Approach
Count frequencies for each character, then compare every pair of distinct characters to see if any share the same count, leading to O(k^2) checks.
Verified Code Solutions
function solution(s) {
const charCount = {};
for (let char of s) {
charCount[char] = (charCount[char] || 0) + 1;
}
const counts = Object.values(charCount);
return new Set(counts).size === counts.length;
}class Solution {
public:
bool solution(string s) {
map<char, int> charCount;
for (char c : s) {
charCount[c]++;
}
int counts[charCount.size()];
int i = 0;
for (auto it = charCount.begin(); it != charCount.end(); ++it) {
counts[i++] = it->second;
}
sort(counts, counts + charCount.size());
for (int i = 0; i < counts.length - 1; i++) {
if (counts[i] == counts[i + 1]) {
return false;
}
}
return true;
}
}class Solution {
public boolean solution(String s) {
Map<Character, Integer> charCount = new HashMap<>();
for (char c : s.toCharArray()) {
charCount.put(c, charCount.getOrDefault(c, 0) + 1);
}
int[] counts = new int[charCount.size()];
int i = 0;
for (int count : charCount.values()) {
counts[i++] = count;
}
Arrays.sort(counts);
for (int i = 0; i < counts.length - 1; i++) {
if (counts[i] == counts[i + 1]) {
return false;
}
}
return true;
}
}def solution(s):
char_count = {}
for char in s:
char_count[char] = char_count.get(char, 0) + 1
counts = list(char_count.values())
return len(set(counts)) == len(counts)function solution(s) {
const charCount = {};
for (let char of s) {
charCount[char] = (charCount[char] || 0) + 1;
}
const counts = Object.values(charCount);
return new Set(counts).size === counts.length;
}Asked in Top Tech Interviews
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.