How do you solve Sherlock and the Valid String using the Frequency-of-Frequencies Test (Optimal) approach?

When to use it: The answer they want — 'count letters, count those counts, then test the two repair shapes'. Count letters into `freq`, then count those frequencies into `ffreq`, a map from 'a frequency value' to 'how many letters have it'. The size of `ffreq` drives the decision. **One distinct frequency → valid.** All letters already appear equally often; no deletion required. **Three or more distinct frequencies → invalid.** A single deletion lowers exactly one letter's count by exactly one. It can reconcile at most two frequency groups, never three. Return `"NO"`. **Exactly two distinct frequencies `lo < hi` — two repair shapes:** 1. **`lo == 1` and a single letter has it.** That letter occurs once; deleting it removes the letter entirely (count 1 → 0) and every survivor shares `hi`. Example: `"aaabbbc"` → counts `{3:2, 1:1}` → delete `c`. 2. **`hi == lo + 1` and a single letter has `hi`.** One letter overshoots by exactly one occurrence; delete one copy (count `hi → lo`) and all letters share `lo`. Example: `"abcc"` → counts `{1:2, 2:1}` → delete one `c`. Every other two-frequency configuration — two letters tied at count 1 (`"aabbcd"`), or a gap greater than one — requires more than one deletion, so it's `"NO"`. **Why O(1) space.** Both maps hold at most 26 entries no matter how long `s` is. Time complexity: O(n). Space complexity: O(1).

Loading…

mediumStrings0Sometimes asked

Sherlock and the Valid String

Q: How do you solve Sherlock and the Valid String using the Brute Force — Delete Every Index and Re-check approach?

When to use it: Use it to anchor correctness, then point out that re-counting after each deletion is the avoidable cost. Start by testing `s` as-is: if all non-zero letter counts are equal, it's valid. Otherwise, for each index `i`, conceptually delete `s[i]`, rebuild the frequency map for the shortened string, and test uniformity. Return `"YES"` at the first deletion that yields uniform counts. **Why it's the obvious first cut.** The statement is operational — 'remove one character and check' — so the direct simulation removes each character and checks. It's correct beyond doubt. **Why it's slow.** Recounting the full string after each of `n` deletions repeats nearly identical work `n` times. For `n = 10⁵`, that's ten billion operations. **Bridge to optimal.** A deletion is fully captured by 'decrement one letter's frequency by one'. So all `n` deletions are knowable from the original frequency map — no string rebuilding required, which leads straight to the frequency-of-frequencies test. Time complexity: O(n²). Space complexity: O(1).

Arrays & Hashing · 81 of 83 · 8 min

Watson asks Sherlock whether a string s is valid. A string is valid when all characters appear the same number of times. It is also valid when removing just one character at one index leaves every remaining character appearing the same number of times.

Return "YES" if s is valid and "NO" otherwise.

In plain English

Validity is a statement about counts, so we count twice. The first count gives each letter's frequency. The second count groups letters by shared frequency. If they all already share one frequency the string is valid; otherwise a single deletion — which lowers exactly one letter's count by one, possibly to zero — must be enough to make every surviving letter agree.

Examples

Example 1

Input: s = "abc"
Output: YES
Note: Frequencies a:1, b:1, c:1 → one distinct frequency → already uniform, valid with no deletion.

Example 2

Input: s = "abcc"
Output: YES
Note: Frequencies a:1, b:1, c:2 → counts {1:2, 2:1}. The higher frequency 2 is one above 1 and held by a single letter 'c' → delete one 'c' → all counts 1.

Example 3

Input: s = "aabbcd"
Output: NO
Note: Frequencies a:2, b:2, c:1, d:1 → counts {2:2, 1:2}. Two letters sit at count 1; one deletion can rescue only one of them.

Example 4

Input: s = "aaaabbbbcccc"
Output: YES
Note: Every letter appears 4 times → one distinct frequency → valid as-is.

Constraints

1 ≤ |s| ≤ 10⁵
s contains lowercase English letters only
At most one character may be removed (zero or one)
Return the literal strings "YES" or "NO"

Clarifying questions4First question: Must I always remove a character, or only if needed?Explore questions

Q1.Must I always remove a character, or only if needed?
Only if needed. An already-uniform string is valid with zero deletions; 'just one character' is the cap, not a requirement.
Q2.Is the single edit a deletion or a substitution?
A deletion at one index. It decreases exactly one letter's frequency by one (to zero if that letter appeared once).
Q3.Could the one deletion be spread across two letters?
No — it is one deletion of one character, affecting a single letter's count.
Q4.What alphabet should I assume?
Lowercase a–z, so the frequency map and the frequency-of-frequencies map are both bounded by 26 — O(1) space.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Reduce the string to two layers of counts. Layer one: how often each letter appears (the frequency map). Layer two: how many letters share each frequency (the frequency-of-frequencies). The string is valid if there is a single distinct frequency, or two distinct frequencies that one deletion can merge — that is, the lower frequency is 1 held by a single letter (delete it whole), or the higher frequency is exactly one above the rest and held by a single letter (delete one of its copies). Everything else is invalid. O(n) time, O(1) space.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you find the two-level count and then enumerate precisely the cases a single deletion can fix, instead of brute-forcing deletions or hand-waving the edge cases.

Where candidates slip

Applying the one-deletion allowance to several letters at once, missing that three distinct frequencies are unfixable, or requiring only the frequency gap without checking it occurs exactly once.

How to stand out

Lead with the invariant — 'a deletion shifts one letter's count down by one' — then derive that valid strings have ≤ 2 distinct frequencies with a single-step, single-occurrence gap, and name the two repair shapes explicitly.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Delete Every Index and Re-check	`O(n²)`	`O(1)`	Use it to anchor correctness, then point out that re-counting after each deletion is the avoidable cost.	Read
2	Frequency-of-Frequencies Test (Optimal)Optimal	`O(n)`	`O(1)`	The answer they want — 'count letters, count those counts, then test the two repair shapes'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewCount letters → freqDistinct frequencies?13+Explore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Delete Every Index and Re-check

TimeO(n²)SpaceO(1)

Use it to anchor correctness, then point out that re-counting after each deletion is the avoidable cost.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The definition is an operation: 'remove one character and check uniformity'. What's the most literal way to test it?

2Hint 2Explore hint

Check the original string first; if not uniform, delete each index in turn and re-test uniformity.

3Hint 3Explore hint

Re-counting for all n deletions is O(n) apiece → O(n²). But each deletion is just decrementing one letter's count, so you can decide it from the original counts.

A · Core idea

Start by testing s as-is: if all non-zero letter counts are equal, it's valid. Otherwise, for each index i, conceptually delete s[i], rebuild the frequency map for the shortened string, and test uniformity. Return "YES" at the first deletion that yields uniform counts.

Why it's the obvious first cut. The statement is operational — 'remove one character and check' — so the direct simulation removes each character and checks. It's correct beyond doubt.

Why it's slow. Recounting the full string after each of n deletions repeats nearly identical work n times. For n = 10⁵, that's ten billion operations.

Bridge to optimal. A deletion is fully captured by 'decrement one letter's frequency by one'. So all n deletions are knowable from the original frequency map — no string rebuilding required, which leads straight to the frequency-of-frequencies test.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "abcc"

Array state

base

a:1, b:1, c:2

a:1

[0]

b:1

[1]

c:2

[2]

Current pointerResolved stateNot processed

Final resultYES

C · Code with teaching comments

Reference implementation previewpublic String isValid(String s) { if (uniform(freqOf(s))) return "YES"; for (int i = 0; i < s.length(); i++) { StringBuilder sb = new StringBuilder(s); sb.deleteCharAt(i);Explore the full code

solution.javaJava

Brute Force — Delete Every Index and Re-check — reference

3 teaching notes

1
public String isValid(String s) {
2
    // Zero-deletion case — the string is already uniform.
3
    if (uniform(freqOf(s))) return "YES";
4
    for (int i = 0; i < s.length(); i++) {
5
        StringBuilder sb = new StringBuilder(s);
6
        // Simulate the single deletion at index i (O(n) per trial).
7
        sb.deleteCharAt(i);
8
        // Full recount — the redundant work the optimal version eliminates.
9
        if (uniform(freqOf(sb.toString()))) {
10
            return "YES";
11
        }
12
    }
13
    return "NO";
14
}
15
 
16
private int[] freqOf(String s) {
17
    int[] f = new int[26];
18
    for (int i = 0; i < s.length(); i++) f[s.charAt(i) - 'a']++;
19
    return f;
20
}
21
 
22
private boolean uniform(int[] f) {
23
    int target = 0;
24
    for (int c : f) {
25
        if (c == 0) continue;
26
        if (target == 0) target = c;
27
        else if (c != target) return false;
28
    }
29
    return true;
30
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.30 lines

D · Why it works and complexityO(n²) timeO(1) spaceOpen the invariant and proofExplore the proof

Because each candidate deletion only nudges one frequency down by one, you can evaluate every possible deletion from the original counts. That observation is what lets the optimal solution skip simulation entirely.

ComplexityO(n²) time, O(1) space — A uniformity check over the 26-letter map is O(n). Trying all n single-character deletions and re-checking is O(n²). The fixed alphabet keeps space O(1).

E · Edge cases and pitfalls3Rebuilding the frequency map for every deletion — O(n²).Explore edge cases

Pitfalls

Rebuilding the frequency map for every deletion — O(n²).
Counting zero-frequency letters as breaking uniformity.
Skipping the zero-deletion check, so already-valid strings fall through.

03.2

Approach 2 of 2 · Optimal

Frequency-of-Frequencies Test (Optimal)

TimeO(n)SpaceO(1)

The answer they want — 'count letters, count those counts, then test the two repair shapes'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

A single deletion shifts exactly one letter's count by one. How many distinct frequency values can survive that?

2Hint 2Explore hint

Build freq, then ffreq = how many letters have each frequency. One distinct frequency ⇒ valid.

3Hint 3Explore hint

With two distinct frequencies lo < hi: valid only if lo == 1 with a single occurrence (delete that letter whole), or hi == lo + 1 with a single occurrence (delete one of its copies). Otherwise NO.

A · Core idea

Count letters into freq, then count those frequencies into ffreq, a map from 'a frequency value' to 'how many letters have it'. The size of ffreq drives the decision.

One distinct frequency → valid. All letters already appear equally often; no deletion required.

Three or more distinct frequencies → invalid. A single deletion lowers exactly one letter's count by exactly one. It can reconcile at most two frequency groups, never three. Return "NO".

Exactly two distinct frequencies `lo < hi` — two repair shapes:

1
`lo == 1` and a single letter has it. That letter occurs once; deleting it removes the letter entirely (count 1 → 0) and every survivor shares hi. Example: "aaabbbc" → counts {3:2, 1:1} → delete c.
2
`hi == lo + 1` and a single letter has `hi`. One letter overshoots by exactly one occurrence; delete one copy (count hi → lo) and all letters share lo. Example: "abcc" → counts {1:2, 2:1} → delete one c.

Every other two-frequency configuration — two letters tied at count 1 ("aabbcd"), or a gap greater than one — requires more than one deletion, so it's "NO".

Why O(1) space. Both maps hold at most 26 entries no matter how long s is.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "abcc"

Array state

freq

a:1, b:1, c:2

a:1

[0]

b:1

[1]

c:2

[2]

Current pointerResolved stateNot processed

Final resultYES

C · Code with teaching comments

solution.javaJava

Frequency-of-Frequencies Test (Optimal) — optimal

4 teaching notes

1
public String isValid(String s) {
2
    int[] freq = new int[26];
3
    for (int i = 0; i < s.length(); i++) freq[s.charAt(i) - 'a']++;
4
    Map<Integer, Integer> ffreq = new HashMap<>();
5
    // Build frequency-of-frequencies — how many letters share each count.
6
    for (int f : freq) {
7
        if (f > 0) ffreq.merge(f, 1, Integer::sum);
8
    }
9
    // One distinct frequency ⇒ uniform already.
10
    if (ffreq.size() == 1) return "YES";
11
    if (ffreq.size() == 2) {
12
        List<Integer> keys = new ArrayList<>(ffreq.keySet());
13
        Collections.sort(keys);
14
        int lo = keys.get(0), hi = keys.get(1);
15
        // Shape 1: a single letter appears once — delete it whole.
16
        if (lo == 1 && ffreq.get(lo) == 1) return "YES";
17
        // Shape 2: a single letter is exactly one too high — delete one copy.
18
        if (hi - lo == 1 && ffreq.get(hi) == 1) return "YES";
19
    }
20
    return "NO";
21
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.21 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

The decisive move is the second count. The first layer exposes each letter's frequency; counting those frequencies reveals whether one deletion can pull everything into agreement. The single-occurrence requirement (ffreq[lo] == 1 or ffreq[hi] == 1) is what stops you from claiming a fix that would actually need several deletions.

ComplexityO(n) time, O(1) space — One O(n) pass builds the frequency map; the rest is constant work over at most 26 frequency values. Both maps are alphabet-bounded → O(1) space.

E · Edge cases and pitfalls8s = "aaa" — freq {a:3} → ffreq {3:1} → one distinct frequency → "YES".Explore edge cases

Edge cases handled

s = "aaa"freq {a:3} → ffreq {3:1} → one distinct frequency → "YES".
s = "aaabbbc"ffreq {3:2, 1:1} → lo==1 and ffreq[lo]==1 → delete lone 'c' → "YES".
s = "aabbcd"ffreq {2:2, 1:2} → two lone letters, neither shape holds → "NO".
s = "aaaaabbbb"ffreq {5:1, 4:1} → hi-lo==1 and ffreq[hi]==1 → delete one 'a' → "YES".

Pitfalls

Spending the single deletion across multiple letters.
Forgetting the three-or-more distinct frequencies → always invalid rule.
Checking only the frequency gap without requiring it to occur exactly once.
Confusing shape 1 (lone count-1 letter) with shape 2 (one-too-high letter).

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic String isValid(String s) { int[] freq = new int[26]; for (int i = 0; i < s.length(); i++) freq[s.charAt(i) - 'a']++; Map<Integer, Integer> ffreq = new HashMap<>(); for (int f : freq) {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Spreading the deletion across letters

"aabbcd" has two count-1 letters; equalising needs two deletions, but only one is allowed, so it is NO.

Explore the code comparison

Don't write this

# wrong: drops all count-1 letters as if each were free
return "YES" if len({v for v in freq.values() if v > 1}) <= 1 else "NO"

Write this instead

if len(ffreq) == 2:
    lo, hi = sorted(ffreq)
    if lo == 1 and ffreq[lo] == 1: return "YES"
    if hi - lo == 1 and ffreq[hi] == 1: return "YES"

Ignoring the three-frequency case

A single deletion moves one letter by one step and cannot reconcile three distinct frequencies, so ffreq.size() >= 3 is always NO.

Explore the code comparison

Don't write this

if (ffreq.size() >= 2) {
    // attempt repair without bounding the number of distinct counts
}

Write this instead

if (ffreq.size() == 1) return "YES";
if (ffreq.size() == 2) { /* test the two shapes */ }
return "NO";

Dropping the single-occurrence guard

hi == lo + 1 isn't sufficient; if two letters share hi, one deletion fixes only one. The offending frequency must occur exactly once.

Explore the code comparison

Don't write this

if hi - lo == 1:
    return "YES"

Write this instead

if hi - lo == 1 and ffreq[hi] == 1:
    return "YES"

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Two-level counting + single-deletion repair test

Code pattern to memorize

freq = Counter(s)
ffreq = Counter(freq.values())
valid = (
  len(ffreq) == 1
  or (len(ffreq) == 2 and (
        (lo == 1 and ffreq[lo] == 1)
     or (hi - lo == 1 and ffreq[hi] == 1)))
)

Rules to remember

1Count the letters, then count those counts — the answer lives in the second layer.
2Already uniform (one distinct frequency) ⇒ valid with no deletion.
3Two distinct frequencies are repairable only in two precise shapes; everything else is not.
4The deletion budget is one character total, not one per letter.
5Three or more distinct frequencies can never be made equal with a single deletion.

Use this pattern when

Decide validity when frequencies must match after removing at most one character
The single edit is a deletion (lowers one letter's count by one)
Fixed lowercase alphabet keeps both count maps O(1)
Goal phrased as 'all characters appear the same number of times'

Choose another pattern when

More than one deletion allowed → generalised k-deletion feasibility
Edit is a replacement → frequency-difference (Anagram) reasoning
Need minimum deletions, not yes/no → sum the surpluses instead
Need to report which character to remove → track the offending letter

Interview takeaway

Collapse the frequency map into a frequency-of-frequencies. Because one deletion moves exactly one letter's count by exactly one, a valid string is locked to at most two frequency values separated by a single, single-occurrence step.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternFrequency of frequencies (two-level counting). When validity hinges on how character counts may differ under a limited number of edits, count the letters and then count those counts. The frequency-of-frequencies map makes the handful of single-edit-repairable shapes explicit.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Sherlock and the Valid String (count-map framing)
Identical frequency-of-frequencies logic stated as a pure validity check.
Unique Number of Occurrences
Coming soon
Tests whether all frequency values are distinct — the same second-level count.
Sort Characters By Frequency
Coming soon
Builds a frequency map then orders by count.
First Unique Character in a String
Frequency map then a scan for the first count-1 letter.

Same pattern

←

Reverse Shuffle Merge

Continue · Next problem

Sherlock and the Valid String

mediumStrings0Sometimes asked

Sherlock and the Valid String

Arrays & Hashing · 81 of 83 · 8 min

Return "YES" if s is valid and "NO" otherwise.

In plain English

Examples

Example 1

Input: s = "abc"
Output: YES
Note: Frequencies a:1, b:1, c:1 → one distinct frequency → already uniform, valid with no deletion.

Example 2

Input: s = "abcc"
Output: YES
Note: Frequencies a:1, b:1, c:2 → counts {1:2, 2:1}. The higher frequency 2 is one above 1 and held by a single letter 'c' → delete one 'c' → all counts 1.

Example 3

Input: s = "aabbcd"
Output: NO
Note: Frequencies a:2, b:2, c:1, d:1 → counts {2:2, 1:2}. Two letters sit at count 1; one deletion can rescue only one of them.

Example 4

Input: s = "aaaabbbbcccc"
Output: YES
Note: Every letter appears 4 times → one distinct frequency → valid as-is.

Constraints

1 ≤ |s| ≤ 10⁵
s contains lowercase English letters only
At most one character may be removed (zero or one)
Return the literal strings "YES" or "NO"

Clarifying questions4First question: Must I always remove a character, or only if needed?Explore questions

Q1.Must I always remove a character, or only if needed?
Only if needed. An already-uniform string is valid with zero deletions; 'just one character' is the cap, not a requirement.
Q2.Is the single edit a deletion or a substitution?
A deletion at one index. It decreases exactly one letter's frequency by one (to zero if that letter appeared once).
Q3.Could the one deletion be spread across two letters?
No — it is one deletion of one character, affecting a single letter's count.
Q4.What alphabet should I assume?
Lowercase a–z, so the frequency map and the frequency-of-frequencies map are both bounded by 26 — O(1) space.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you find the two-level count and then enumerate precisely the cases a single deletion can fix, instead of brute-forcing deletions or hand-waving the edge cases.

Where candidates slip

Applying the one-deletion allowance to several letters at once, missing that three distinct frequencies are unfixable, or requiring only the frequency gap without checking it occurs exactly once.

How to stand out

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Delete Every Index and Re-check	`O(n²)`	`O(1)`	Use it to anchor correctness, then point out that re-counting after each deletion is the avoidable cost.	Read
2	Frequency-of-Frequencies Test (Optimal)Optimal	`O(n)`	`O(1)`	The answer they want — 'count letters, count those counts, then test the two repair shapes'.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Delete Every Index and Re-check

TimeO(n²)SpaceO(1)

Use it to anchor correctness, then point out that re-counting after each deletion is the avoidable cost.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The definition is an operation: 'remove one character and check uniformity'. What's the most literal way to test it?

2Hint 2Explore hint

Check the original string first; if not uniform, delete each index in turn and re-test uniformity.

3Hint 3Explore hint

Re-counting for all n deletions is O(n) apiece → O(n²). But each deletion is just decrementing one letter's count, so you can decide it from the original counts.

A · Core idea

Why it's the obvious first cut. The statement is operational — 'remove one character and check' — so the direct simulation removes each character and checks. It's correct beyond doubt.

Why it's slow. Recounting the full string after each of n deletions repeats nearly identical work n times. For n = 10⁵, that's ten billion operations.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "abcc"

Array state

base

a:1, b:1, c:2

a:1

[0]

b:1

[1]

c:2

[2]

Current pointerResolved stateNot processed

Final resultYES

C · Code with teaching comments

solution.javaJava

Brute Force — Delete Every Index and Re-check — reference

3 teaching notes

1
public String isValid(String s) {
2
    // Zero-deletion case — the string is already uniform.
3
    if (uniform(freqOf(s))) return "YES";
4
    for (int i = 0; i < s.length(); i++) {
5
        StringBuilder sb = new StringBuilder(s);
6
        // Simulate the single deletion at index i (O(n) per trial).
7
        sb.deleteCharAt(i);
8
        // Full recount — the redundant work the optimal version eliminates.
9
        if (uniform(freqOf(sb.toString()))) {
10
            return "YES";
11
        }
12
    }
13
    return "NO";
14
}
15
 
16
private int[] freqOf(String s) {
17
    int[] f = new int[26];
18
    for (int i = 0; i < s.length(); i++) f[s.charAt(i) - 'a']++;
19
    return f;
20
}
21
 
22
private boolean uniform(int[] f) {
23
    int target = 0;
24
    for (int c : f) {
25
        if (c == 0) continue;
26
        if (target == 0) target = c;
27
        else if (c != target) return false;
28
    }
29
    return true;
30
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.30 lines

D · Why it works and complexityO(n²) timeO(1) spaceOpen the invariant and proofExplore the proof

ComplexityO(n²) time, O(1) space — A uniformity check over the 26-letter map is O(n). Trying all n single-character deletions and re-checking is O(n²). The fixed alphabet keeps space O(1).

E · Edge cases and pitfalls3Rebuilding the frequency map for every deletion — O(n²).Explore edge cases

Pitfalls

Rebuilding the frequency map for every deletion — O(n²).
Counting zero-frequency letters as breaking uniformity.
Skipping the zero-deletion check, so already-valid strings fall through.

03.2

Approach 2 of 2 · Optimal

Frequency-of-Frequencies Test (Optimal)

TimeO(n)SpaceO(1)

The answer they want — 'count letters, count those counts, then test the two repair shapes'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

A single deletion shifts exactly one letter's count by one. How many distinct frequency values can survive that?

2Hint 2Explore hint

Build freq, then ffreq = how many letters have each frequency. One distinct frequency ⇒ valid.

3Hint 3Explore hint

With two distinct frequencies lo < hi: valid only if lo == 1 with a single occurrence (delete that letter whole), or hi == lo + 1 with a single occurrence (delete one of its copies). Otherwise NO.

A · Core idea

Count letters into freq, then count those frequencies into ffreq, a map from 'a frequency value' to 'how many letters have it'. The size of ffreq drives the decision.

One distinct frequency → valid. All letters already appear equally often; no deletion required.

Three or more distinct frequencies → invalid. A single deletion lowers exactly one letter's count by exactly one. It can reconcile at most two frequency groups, never three. Return "NO".

Exactly two distinct frequencies `lo < hi` — two repair shapes:

1
`lo == 1` and a single letter has it. That letter occurs once; deleting it removes the letter entirely (count 1 → 0) and every survivor shares hi. Example: "aaabbbc" → counts {3:2, 1:1} → delete c.
2
`hi == lo + 1` and a single letter has `hi`. One letter overshoots by exactly one occurrence; delete one copy (count hi → lo) and all letters share lo. Example: "abcc" → counts {1:2, 2:1} → delete one c.

Every other two-frequency configuration — two letters tied at count 1 ("aabbcd"), or a gap greater than one — requires more than one deletion, so it's "NO".

Why O(1) space. Both maps hold at most 26 entries no matter how long s is.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "abcc"

Array state

freq

a:1, b:1, c:2

a:1

[0]

b:1

[1]

c:2

[2]

Current pointerResolved stateNot processed

Final resultYES

C · Code with teaching comments

solution.javaJava

Frequency-of-Frequencies Test (Optimal) — optimal

4 teaching notes

1
public String isValid(String s) {
2
    int[] freq = new int[26];
3
    for (int i = 0; i < s.length(); i++) freq[s.charAt(i) - 'a']++;
4
    Map<Integer, Integer> ffreq = new HashMap<>();
5
    // Build frequency-of-frequencies — how many letters share each count.
6
    for (int f : freq) {
7
        if (f > 0) ffreq.merge(f, 1, Integer::sum);
8
    }
9
    // One distinct frequency ⇒ uniform already.
10
    if (ffreq.size() == 1) return "YES";
11
    if (ffreq.size() == 2) {
12
        List<Integer> keys = new ArrayList<>(ffreq.keySet());
13
        Collections.sort(keys);
14
        int lo = keys.get(0), hi = keys.get(1);
15
        // Shape 1: a single letter appears once — delete it whole.
16
        if (lo == 1 && ffreq.get(lo) == 1) return "YES";
17
        // Shape 2: a single letter is exactly one too high — delete one copy.
18
        if (hi - lo == 1 && ffreq.get(hi) == 1) return "YES";
19
    }
20
    return "NO";
21
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.21 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

ComplexityO(n) time, O(1) space — One O(n) pass builds the frequency map; the rest is constant work over at most 26 frequency values. Both maps are alphabet-bounded → O(1) space.

E · Edge cases and pitfalls8s = "aaa" — freq {a:3} → ffreq {3:1} → one distinct frequency → "YES".Explore edge cases

Edge cases handled

s = "aaa"freq {a:3} → ffreq {3:1} → one distinct frequency → "YES".
s = "aaabbbc"ffreq {3:2, 1:1} → lo==1 and ffreq[lo]==1 → delete lone 'c' → "YES".
s = "aabbcd"ffreq {2:2, 1:2} → two lone letters, neither shape holds → "NO".
s = "aaaaabbbb"ffreq {5:1, 4:1} → hi-lo==1 and ffreq[hi]==1 → delete one 'a' → "YES".

Pitfalls

Spending the single deletion across multiple letters.
Forgetting the three-or-more distinct frequencies → always invalid rule.
Checking only the frequency gap without requiring it to occur exactly once.
Confusing shape 1 (lone count-1 letter) with shape 2 (one-too-high letter).

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Spreading the deletion across letters

"aabbcd" has two count-1 letters; equalising needs two deletions, but only one is allowed, so it is NO.

Explore the code comparison

Don't write this

# wrong: drops all count-1 letters as if each were free
return "YES" if len({v for v in freq.values() if v > 1}) <= 1 else "NO"

Write this instead

if len(ffreq) == 2:
    lo, hi = sorted(ffreq)
    if lo == 1 and ffreq[lo] == 1: return "YES"
    if hi - lo == 1 and ffreq[hi] == 1: return "YES"

Ignoring the three-frequency case

A single deletion moves one letter by one step and cannot reconcile three distinct frequencies, so ffreq.size() >= 3 is always NO.

Explore the code comparison

Don't write this

if (ffreq.size() >= 2) {
    // attempt repair without bounding the number of distinct counts
}

Write this instead

if (ffreq.size() == 1) return "YES";
if (ffreq.size() == 2) { /* test the two shapes */ }
return "NO";

Dropping the single-occurrence guard

hi == lo + 1 isn't sufficient; if two letters share hi, one deletion fixes only one. The offending frequency must occur exactly once.

Explore the code comparison

Don't write this

if hi - lo == 1:
    return "YES"

Write this instead

if hi - lo == 1 and ffreq[hi] == 1:
    return "YES"

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Two-level counting + single-deletion repair test

Code pattern to memorize

freq = Counter(s)
ffreq = Counter(freq.values())
valid = (
  len(ffreq) == 1
  or (len(ffreq) == 2 and (
        (lo == 1 and ffreq[lo] == 1)
     or (hi - lo == 1 and ffreq[hi] == 1)))
)

Rules to remember

1Count the letters, then count those counts — the answer lives in the second layer.
2Already uniform (one distinct frequency) ⇒ valid with no deletion.
3Two distinct frequencies are repairable only in two precise shapes; everything else is not.
4The deletion budget is one character total, not one per letter.
5Three or more distinct frequencies can never be made equal with a single deletion.

Use this pattern when

Decide validity when frequencies must match after removing at most one character
The single edit is a deletion (lowers one letter's count by one)
Fixed lowercase alphabet keeps both count maps O(1)
Goal phrased as 'all characters appear the same number of times'

Choose another pattern when

More than one deletion allowed → generalised k-deletion feasibility
Edit is a replacement → frequency-difference (Anagram) reasoning
Need minimum deletions, not yes/no → sum the surpluses instead
Need to report which character to remove → track the offending letter

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Sherlock and the Valid String (count-map framing)
Identical frequency-of-frequencies logic stated as a pure validity check.
Unique Number of Occurrences
Coming soon
Tests whether all frequency values are distinct — the same second-level count.
Sort Characters By Frequency
Coming soon
Builds a frequency map then orders by count.
First Unique Character in a String
Frequency map then a scan for the first count-1 letter.

Same pattern

←

Reverse Shuffle Merge

Continue · Next problem

Sherlock and the Valid String