Loading…

mediumStrings0Sometimes asked

Sherlock and the Valid String

Q: How do you solve Sherlock and the Valid String using the Brute Force — Try Deleting Each Character approach?

When to use it: Mention to prove correctness intuition, then note that recomputing frequencies after each candidate deletion is wasteful. Simulate the definition literally. First check whether `s` is already valid: build the frequency map and confirm all non-zero counts are equal. If it is, return `"YES"`. Otherwise, for each index `i`, imagine deleting `s[i]`, rebuild the frequencies, and test uniformity; return `"YES"` the moment one deletion works. **Why this is the natural first attempt.** The problem is phrased as an operation — 'remove exactly one character' — so the mechanical response is to perform every possible removal and check the result. It is unquestionably correct. **Why it's wasteful.** Re-counting the entire string after each of the `n` candidate deletions repeats almost identical work `n` times. For `n = 10⁵` that's ten billion operations. Everything we learn from a deletion is already encoded in the original frequency map — deleting one copy of letter `x` just decrements `freq[x]` by one. **The bridge to optimal.** Because a deletion only nudges one letter's count down by one, you never need to mutate the string at all. Summarising the frequency map by *how many letters share each count* tells you in O(1) whether a single decrement can equalise everything. Time complexity: O(n²). Space complexity: O(1).

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

When to use it: The answer they want — frame it as 'count the letters, then count those counts, then test the two repair shapes'. Count letters into `freq`, then count those frequencies into `counts` (a map from 'a frequency value' to 'how many letters have it'). The number of distinct keys in `counts` decides almost everything. **One distinct frequency → valid immediately.** Every letter already appears the same number of times; no deletion needed. **Three or more distinct frequencies → impossible.** A single deletion changes exactly one letter's count by exactly one. That can collapse at most two frequency groups into agreement; it can never reconcile three different values. Return `"NO"`. **Exactly two distinct frequencies f1 < f2 — only two repair shapes work:** 1. **`f1 == 1` and only one letter has it.** That lone letter appears once; delete it entirely (its count goes 1 → 0, dropping out) and every remaining letter shares frequency `f2`. Example: `"aabbc"` → counts `{2:2, 1:1}` → delete `c`. 2. **`f2 == f1 + 1` and only one letter has `f2`.** One letter sticks out by a single extra occurrence; delete one copy of it (its count goes `f2 → f1`) and all letters share `f1`. Example: `"aabbccc"` → counts `{2:2, 3:1}` → delete one `c`. Any other two-frequency shape — two lone letters (`"aabbcd"` → `{2:2, 1:2}`), or a gap larger than one (`"aaabbbbcc"`-style) — needs more than one deletion, so it's `"NO"`. **Why O(1) space.** Both the frequency map and the frequency-of-frequencies map have at most 26 entries regardless of `n`. Time complexity: O(n). Space complexity: O(1).

Arrays & Hashing · 82 of 83 · 8 min

A string is valid if all of its characters appear the same number of times. It is also valid if you can remove exactly one character at one index in the string, and the remaining characters then all appear the same number of times.

Given a string s, return "YES" if it is valid, otherwise "NO".

In plain English

Two layers of counting decide everything. First, count how often each letter appears. Then count how many letters share each frequency. If every letter already has the same frequency, the string is valid as-is. Otherwise there can be at most two distinct frequencies, and a single deletion (which lowers exactly one letter's count by one, possibly to zero) must be enough to make them all equal.

Examples

Example 1

Input: s = "aabbcd"
Output: NO
Note: Frequencies a:2, b:2, c:1, d:1 → counts {2:2, 1:2}. Two letters have count 1, so one deletion can fix only one of them; the other still breaks equality.

Example 2

Input: s = "aabbc"
Output: YES
Note: Frequencies a:2, b:2, c:1 → counts {2:2, 1:1}. The lone count-1 letter 'c' can be deleted entirely, leaving a:2, b:2 — all equal.

Example 3

Input: s = "aabbccddeefghi"
Output: NO
Note: a,b,c,d,e have count 2 but f,g,h,i have count 1 → counts {2:5, 1:4}. Four lone letters means four deletions needed — more than one allowed.

Example 4

Input: s = "abcdefghhgfedecba"
Output: YES
Note: Every letter appears twice except one appears three times → counts {2:?, 3:1}. Deleting one occurrence of the triple makes all counts 2.

Constraints

1 ≤ |s| ≤ 10⁵
s consists of lowercase English letters only
You may delete at most one character total (zero or one)
Return the literal strings "YES" or "NO"

Clarifying questions4First question: Does 'remove exactly one character' mean I must delete, or may delete?Explore questions

Q1.Does 'remove exactly one character' mean I must delete, or may delete?
May — zero deletions is allowed if the string is already valid. The 'exactly one' refers to the maximum you're permitted when a repair is needed.
Q2.Is the edit a deletion or a replacement?
A deletion: you drop one character at one index. That lowers exactly one letter's frequency by one (possibly to zero).
Q3.Can I delete one character from several letters?
No. At most one deletion total, affecting exactly one letter's count by one.
Q4.What's the alphabet?
Lowercase a–z, so both the frequency map and the frequency-of-frequencies map are O(1) in size.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Build the character-frequency map, then build a frequency-of-frequencies map (how many letters share each count). A string is valid if (a) all letters already share one count, or (b) there are exactly two distinct counts and you can delete exactly one character of one letter to merge them. Case (b) holds when the smaller count is 1 occurring once (delete that lone letter), or the larger count is exactly 1 more than the smaller and occurs only once (delete one occurrence of that letter). Otherwise invalid. O(n) time, O(1) space.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you reach for a two-level count (frequency of frequencies) and then enumerate the exact handful of cases a single deletion can repair, rather than trying random deletions.

Where candidates slip

Allowing the 'delete one' to apply per-letter, or forgetting that three distinct frequencies can never be fixed; also mishandling the count-1 case (e.g. "aabbc") versus the count-too-high case (e.g. "aabbccc").

How to stand out

State the invariant first: 'one deletion changes exactly one letter's count by one, so a valid string has at most two distinct frequencies and the gap must be 1-with-single-occurrence — or one of the counts is a lone 1.' Then list the two repair shapes.

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 — Try Deleting Each Character	`O(n²)`	`O(1)`	Mention to prove correctness intuition, then note that recomputing frequencies after each candidate deletion is wasteful.	Read
2	Frequency of Frequencies (Optimal)Optimal	`O(n)`	`O(1)`	The answer they want — frame it as 'count the letters, then 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 previewfreq = count lettersHow many distinct counts?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 — Try Deleting Each Character

TimeO(n²)SpaceO(1)

Mention to prove correctness intuition, then note that recomputing frequencies after each candidate deletion is wasteful.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The definition is operational: 'remove exactly one character and check if the rest are uniform'. What's the most direct simulation?

2Hint 2Explore hint

First test whether the string is already valid (all frequencies equal). If not, try removing each index in turn and re-test.

3Hint 3Explore hint

Re-counting frequencies for all n candidate deletions is O(n) each → O(n²). Correct, but you can decide everything from the original counts alone.

A · Core idea

Simulate the definition literally. First check whether s is already valid: build the frequency map and confirm all non-zero counts are equal. If it is, return "YES". Otherwise, for each index i, imagine deleting s[i], rebuild the frequencies, and test uniformity; return "YES" the moment one deletion works.

Why this is the natural first attempt. The problem is phrased as an operation — 'remove exactly one character' — so the mechanical response is to perform every possible removal and check the result. It is unquestionably correct.

Why it's wasteful. Re-counting the entire string after each of the n candidate deletions repeats almost identical work n times. For n = 10⁵ that's ten billion operations. Everything we learn from a deletion is already encoded in the original frequency map — deleting one copy of letter x just decrements freq[x] by one.

The bridge to optimal. Because a deletion only nudges one letter's count down by one, you never need to mutate the string at all. Summarising the frequency map by how many letters share each count tells you in O(1) whether a single decrement can equalise everything.

B · Visual dry run

Interactive dry run

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

s = "aabbc"

Array state

base

a:2, b:2, c:1

a:2

[0]

b:2

[1]

c:1

[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 — Try Deleting Each Character — reference

3 teaching notes

1
public String isValid(String s) {
2
    // Zero-deletion case — already valid.
3
    if (uniform(freqOf(s))) return "YES";
4
    for (int i = 0; i < s.length(); i++) {
5
        StringBuilder sb = new StringBuilder(s);
6
        // Simulate deleting one character at index i (the O(n) cost per trial).
7
        sb.deleteCharAt(i);
8
        // Re-count from scratch — the redundant work the optimal version removes.
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

A single deletion is fully described by 'decrement one entry of the frequency map by one'. That means you can reason about all n possible deletions from the frequency map alone, without ever rebuilding the string — which is exactly what the optimal frequency-of-frequencies approach does.

ComplexityO(n²) time, O(1) space — Checking uniformity is O(n) over a 26-letter map. Trying every one of n deletions and re-checking is O(n²). The alphabet-sized maps keep space O(1).

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

Pitfalls

Rebuilding the full frequency map for every candidate deletion — O(n²).
Treating count-0 letters as breaking uniformity — ignore zeros.
Forgetting the zero-deletion (already valid) check before trying deletions.

03.2

Approach 2 of 2 · Optimal

Frequency of Frequencies (Optimal)

TimeO(n)SpaceO(1)

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

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

A deletion lowers exactly one letter's count by one. So how many DISTINCT counts can a valid string tolerate?

2Hint 2Explore hint

Build freq = count of each letter, then counts = count of each frequency value. If there's only one distinct frequency, it's already valid.

3Hint 3Explore hint

If there are exactly two distinct frequencies f1 < f2, it's valid only when f1 == 1 with a single occurrence (delete that lone letter), or f2 == f1 + 1 with a single occurrence (delete one from that letter). Any other shape, or three+ frequencies, is NO.

A · Core idea

Count letters into freq, then count those frequencies into counts (a map from 'a frequency value' to 'how many letters have it'). The number of distinct keys in counts decides almost everything.

One distinct frequency → valid immediately. Every letter already appears the same number of times; no deletion needed.

Three or more distinct frequencies → impossible. A single deletion changes exactly one letter's count by exactly one. That can collapse at most two frequency groups into agreement; it can never reconcile three different values. Return "NO".

Exactly two distinct frequencies f1 < f2 — only two repair shapes work:

1
`f1 == 1` and only one letter has it. That lone letter appears once; delete it entirely (its count goes 1 → 0, dropping out) and every remaining letter shares frequency f2. Example: "aabbc" → counts {2:2, 1:1} → delete c.
2
`f2 == f1 + 1` and only one letter has `f2`. One letter sticks out by a single extra occurrence; delete one copy of it (its count goes f2 → f1) and all letters share f1. Example: "aabbccc" → counts {2:2, 3:1} → delete one c.

Any other two-frequency shape — two lone letters ("aabbcd" → {2:2, 1:2}), or a gap larger than one ("aaabbbbcc"-style) — needs more than one deletion, so it's "NO".

Why O(1) space. Both the frequency map and the frequency-of-frequencies map have at most 26 entries regardless of n.

B · Visual dry run

Interactive dry run

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

s = "aabbcd"

Array state

freq

a:2, b:2, c:1, d:1

a:2

[0]

b:2

[1]

c:1

[2]

d:1

[3]

Current pointerResolved stateNot processed

Final resultNO

C · Code with teaching comments

solution.javaJava

Frequency of Frequencies (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> counts = new HashMap<>();
5
    // Build the frequency-of-frequencies: how many letters share each count.
6
    for (int f : freq) {
7
        if (f > 0) counts.merge(f, 1, Integer::sum);
8
    }
9
    // One distinct frequency ⇒ already uniform.
10
    if (counts.size() == 1) return "YES";
11
    if (counts.size() == 2) {
12
        List<Integer> keys = new ArrayList<>(counts.keySet());
13
        Collections.sort(keys);
14
        int f1 = keys.get(0), f2 = keys.get(1);
15
        int c1 = counts.get(f1), c2 = counts.get(f2);
16
        // Shape 1: a single lone letter with count 1 — delete it whole.
17
        if (f1 == 1 && c1 == 1) return "YES";
18
        // Shape 2: one letter exactly one above the rest — delete one of its copies.
19
        if (f2 - f1 == 1 && c2 == 1) return "YES";
20
    }
21
    return "NO";
22
}

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

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

The leap is the second level of counting. The first count tells you each letter's frequency; counting those frequencies exposes the structure a single deletion can repair. Because one deletion moves one letter by one step, a valid string is pinned to at most two frequency values with a one-step, single-occurrence gap.

ComplexityO(n) time, O(1) space — One pass to build the frequency map (O(n)), then constant work over at most 26 frequency values. Both maps are bounded by the 26-letter alphabet, so space is O(1).

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

Edge cases handled

s = "a"freq {a:1} → counts {1:1} → one distinct frequency → "YES".
s = "aabbccc"counts {2:2, 3:1} → f2-f1==1 and c2==1 → delete one 'c' → "YES".
s = "aaabbbcccd"counts {3:3, 1:1} → f1==1 c1==1 → delete lone 'd' → "YES".
s = "aaaabbbb"counts {4:2} → one distinct frequency → "YES" with no deletion.

Pitfalls

Allowing the deletion per-letter — only ONE deletion total is permitted.
Forgetting that three or more distinct frequencies is always invalid.
Mixing up the two repair shapes — count-1-once (delete whole) versus gap-of-1-once (delete one copy).
Not requiring the offending frequency to occur exactly once (c1 == 1 or c2 == 1).

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> counts = 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.

Treating the deletion as per-letter

"aabbcd" has two letters with count 1; fixing both needs two deletions. Only one deletion is allowed, so it must be NO.

Explore the code comparison

Don't write this

# wrong: assumes any single-count letters can all be dropped
return "YES" if all(c in (1, base) for c in freq.values()) else "NO"

Write this instead

if len(counts) == 2:
    (f1, c1), (f2, c2) = sorted(counts.items())
    if f1 == 1 and c1 == 1: return "YES"
    if f2 - f1 == 1 and c2 == 1: return "YES"

Ignoring the three-frequency impossibility

One deletion shifts a single letter's count by one — it can't reconcile three different frequency values, so any counts.size() >= 3 is NO.

Explore the code comparison

Don't write this

if (counts.size() >= 2) {
    // try to repair regardless of how many distinct counts
}

Write this instead

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

Dropping the single-occurrence requirement

f2 - f1 == 1 alone isn't enough; if two letters share the higher count (c2 > 1), deleting one fixes only one of them. The offending frequency must occur exactly once.

Explore the code comparison

Don't write this

if f2 - f1 == 1:
    return "YES"

Write this instead

if f2 - f1 == 1 and c2 == 1:
    return "YES"

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Frequency of frequencies (two-level counting)

Code pattern to memorize

freq = Counter(s)
counts = Counter(freq.values())
if len(counts) == 1: VALID
if len(counts) == 2:
    (f1,c1),(f2,c2) = sorted(counts.items())  # f1 < f2
    VALID if (f1 == 1 and c1 == 1) or (f2 - f1 == 1 and c2 == 1)
else: INVALID

Rules to remember

1Count twice: first letters → frequencies, then frequencies → how many letters have them.
2One distinct frequency ⇒ already valid, no deletion needed.
3Three or more distinct frequencies ⇒ impossible — one deletion changes only one letter's count by one.
4With two frequencies, only two repair shapes work: a lone count-1 letter you can delete entirely, or a single letter whose count is exactly one above the rest.
5You may delete at most one character total — not one per letter.

Use this pattern when

Asked if frequencies can be equalised by removing at most one character
Counts must all match after a single edit, and the edit is a deletion
Small fixed alphabet, so frequency-of-frequencies is tiny (O(1))
You see 'all characters appear the same number of times' as the goal

Choose another pattern when

Allowed to delete more than one character → that's a different (k-deletion) problem
Edit is a replacement, not a deletion → Anagram-style frequency-difference instead
Need to find WHICH character to delete → track the offending letter, not just yes/no
Need the minimum deletions to make valid → count surpluses, don't just test feasibility

Interview takeaway

The trick is the second level of counting: collapse the frequency map into a frequency-of-frequencies. A valid string can have at most two distinct counts, and the gap between them must be repairable by deleting a single character — which is only true in two narrow shapes.

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 a problem constrains how character counts may differ — especially under a bounded number of edits — count the letters, then count those counts. The compact frequency-of-frequencies map exposes exactly which repairs a single edit can achieve.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Sherlock and the Valid String (alternate framing)
Same frequency-of-frequencies logic under a slightly different problem statement.
Sort Characters By Frequency
Coming soon
Also built on a frequency map, then ordering by count.
Unique Number of Occurrences
Coming soon
Directly asks whether all frequency values are distinct — the same second-level count.
Valid Anagram
Frequency comparison between two strings rather than within one.

Same pattern

←

Sherlock and the Valid String

Continue · Next problem

Two Strings

mediumStrings0Sometimes asked

Sherlock and the Valid String

Arrays & Hashing · 82 of 83 · 8 min

Given a string s, return "YES" if it is valid, otherwise "NO".

In plain English

Examples

Example 1

Input: s = "aabbcd"
Output: NO
Note: Frequencies a:2, b:2, c:1, d:1 → counts {2:2, 1:2}. Two letters have count 1, so one deletion can fix only one of them; the other still breaks equality.

Example 2

Input: s = "aabbc"
Output: YES
Note: Frequencies a:2, b:2, c:1 → counts {2:2, 1:1}. The lone count-1 letter 'c' can be deleted entirely, leaving a:2, b:2 — all equal.

Example 3

Input: s = "aabbccddeefghi"
Output: NO
Note: a,b,c,d,e have count 2 but f,g,h,i have count 1 → counts {2:5, 1:4}. Four lone letters means four deletions needed — more than one allowed.

Example 4

Input: s = "abcdefghhgfedecba"
Output: YES
Note: Every letter appears twice except one appears three times → counts {2:?, 3:1}. Deleting one occurrence of the triple makes all counts 2.

Constraints

1 ≤ |s| ≤ 10⁵
s consists of lowercase English letters only
You may delete at most one character total (zero or one)
Return the literal strings "YES" or "NO"

Clarifying questions4First question: Does 'remove exactly one character' mean I must delete, or may delete?Explore questions

Q1.Does 'remove exactly one character' mean I must delete, or may delete?
May — zero deletions is allowed if the string is already valid. The 'exactly one' refers to the maximum you're permitted when a repair is needed.
Q2.Is the edit a deletion or a replacement?
A deletion: you drop one character at one index. That lowers exactly one letter's frequency by one (possibly to zero).
Q3.Can I delete one character from several letters?
No. At most one deletion total, affecting exactly one letter's count by one.
Q4.What's the alphabet?
Lowercase a–z, so both the frequency map and the frequency-of-frequencies map are O(1) in size.

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 reach for a two-level count (frequency of frequencies) and then enumerate the exact handful of cases a single deletion can repair, rather than trying random deletions.

Where candidates slip

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 — Try Deleting Each Character	`O(n²)`	`O(1)`	Mention to prove correctness intuition, then note that recomputing frequencies after each candidate deletion is wasteful.	Read
2	Frequency of Frequencies (Optimal)Optimal	`O(n)`	`O(1)`	The answer they want — frame it as 'count the letters, then 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 — Try Deleting Each Character

TimeO(n²)SpaceO(1)

Mention to prove correctness intuition, then note that recomputing frequencies after each candidate deletion is wasteful.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The definition is operational: 'remove exactly one character and check if the rest are uniform'. What's the most direct simulation?

2Hint 2Explore hint

First test whether the string is already valid (all frequencies equal). If not, try removing each index in turn and re-test.

3Hint 3Explore hint

Re-counting frequencies for all n candidate deletions is O(n) each → O(n²). Correct, but you can decide everything from the original counts alone.

A · Core idea

B · Visual dry run

Interactive dry run

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

s = "aabbc"

Array state

base

a:2, b:2, c:1

a:2

[0]

b:2

[1]

c:1

[2]

Current pointerResolved stateNot processed

Final resultYES

C · Code with teaching comments

solution.javaJava

Brute Force — Try Deleting Each Character — reference

3 teaching notes

1
public String isValid(String s) {
2
    // Zero-deletion case — already valid.
3
    if (uniform(freqOf(s))) return "YES";
4
    for (int i = 0; i < s.length(); i++) {
5
        StringBuilder sb = new StringBuilder(s);
6
        // Simulate deleting one character at index i (the O(n) cost per trial).
7
        sb.deleteCharAt(i);
8
        // Re-count from scratch — the redundant work the optimal version removes.
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 — Checking uniformity is O(n) over a 26-letter map. Trying every one of n deletions and re-checking is O(n²). The alphabet-sized maps keep space O(1).

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

Pitfalls

Rebuilding the full frequency map for every candidate deletion — O(n²).
Treating count-0 letters as breaking uniformity — ignore zeros.
Forgetting the zero-deletion (already valid) check before trying deletions.

03.2

Approach 2 of 2 · Optimal

Frequency of Frequencies (Optimal)

TimeO(n)SpaceO(1)

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

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

A deletion lowers exactly one letter's count by one. So how many DISTINCT counts can a valid string tolerate?

2Hint 2Explore hint

Build freq = count of each letter, then counts = count of each frequency value. If there's only one distinct frequency, it's already valid.

3Hint 3Explore hint

A · Core idea

One distinct frequency → valid immediately. Every letter already appears the same number of times; no deletion needed.

Exactly two distinct frequencies f1 < f2 — only two repair shapes work:

1
`f1 == 1` and only one letter has it. That lone letter appears once; delete it entirely (its count goes 1 → 0, dropping out) and every remaining letter shares frequency f2. Example: "aabbc" → counts {2:2, 1:1} → delete c.
2
`f2 == f1 + 1` and only one letter has `f2`. One letter sticks out by a single extra occurrence; delete one copy of it (its count goes f2 → f1) and all letters share f1. Example: "aabbccc" → counts {2:2, 3:1} → delete one c.

Any other two-frequency shape — two lone letters ("aabbcd" → {2:2, 1:2}), or a gap larger than one ("aaabbbbcc"-style) — needs more than one deletion, so it's "NO".

Why O(1) space. Both the frequency map and the frequency-of-frequencies map have at most 26 entries regardless of n.

B · Visual dry run

Interactive dry run

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

s = "aabbcd"

Array state

freq

a:2, b:2, c:1, d:1

a:2

[0]

b:2

[1]

c:1

[2]

d:1

[3]

Current pointerResolved stateNot processed

Final resultNO

C · Code with teaching comments

solution.javaJava

Frequency of Frequencies (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> counts = new HashMap<>();
5
    // Build the frequency-of-frequencies: how many letters share each count.
6
    for (int f : freq) {
7
        if (f > 0) counts.merge(f, 1, Integer::sum);
8
    }
9
    // One distinct frequency ⇒ already uniform.
10
    if (counts.size() == 1) return "YES";
11
    if (counts.size() == 2) {
12
        List<Integer> keys = new ArrayList<>(counts.keySet());
13
        Collections.sort(keys);
14
        int f1 = keys.get(0), f2 = keys.get(1);
15
        int c1 = counts.get(f1), c2 = counts.get(f2);
16
        // Shape 1: a single lone letter with count 1 — delete it whole.
17
        if (f1 == 1 && c1 == 1) return "YES";
18
        // Shape 2: one letter exactly one above the rest — delete one of its copies.
19
        if (f2 - f1 == 1 && c2 == 1) return "YES";
20
    }
21
    return "NO";
22
}

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

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

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

Edge cases handled

s = "a"freq {a:1} → counts {1:1} → one distinct frequency → "YES".
s = "aabbccc"counts {2:2, 3:1} → f2-f1==1 and c2==1 → delete one 'c' → "YES".
s = "aaabbbcccd"counts {3:3, 1:1} → f1==1 c1==1 → delete lone 'd' → "YES".
s = "aaaabbbb"counts {4:2} → one distinct frequency → "YES" with no deletion.

Pitfalls

Allowing the deletion per-letter — only ONE deletion total is permitted.
Forgetting that three or more distinct frequencies is always invalid.
Mixing up the two repair shapes — count-1-once (delete whole) versus gap-of-1-once (delete one copy).
Not requiring the offending frequency to occur exactly once (c1 == 1 or c2 == 1).

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.

Treating the deletion as per-letter

"aabbcd" has two letters with count 1; fixing both needs two deletions. Only one deletion is allowed, so it must be NO.

Explore the code comparison

Don't write this

# wrong: assumes any single-count letters can all be dropped
return "YES" if all(c in (1, base) for c in freq.values()) else "NO"

Write this instead

if len(counts) == 2:
    (f1, c1), (f2, c2) = sorted(counts.items())
    if f1 == 1 and c1 == 1: return "YES"
    if f2 - f1 == 1 and c2 == 1: return "YES"

Ignoring the three-frequency impossibility

One deletion shifts a single letter's count by one — it can't reconcile three different frequency values, so any counts.size() >= 3 is NO.

Explore the code comparison

Don't write this

if (counts.size() >= 2) {
    // try to repair regardless of how many distinct counts
}

Write this instead

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

Dropping the single-occurrence requirement

f2 - f1 == 1 alone isn't enough; if two letters share the higher count (c2 > 1), deleting one fixes only one of them. The offending frequency must occur exactly once.

Explore the code comparison

Don't write this

if f2 - f1 == 1:
    return "YES"

Write this instead

if f2 - f1 == 1 and c2 == 1:
    return "YES"

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Frequency of frequencies (two-level counting)

Code pattern to memorize

freq = Counter(s)
counts = Counter(freq.values())
if len(counts) == 1: VALID
if len(counts) == 2:
    (f1,c1),(f2,c2) = sorted(counts.items())  # f1 < f2
    VALID if (f1 == 1 and c1 == 1) or (f2 - f1 == 1 and c2 == 1)
else: INVALID

Rules to remember

1Count twice: first letters → frequencies, then frequencies → how many letters have them.
2One distinct frequency ⇒ already valid, no deletion needed.
3Three or more distinct frequencies ⇒ impossible — one deletion changes only one letter's count by one.
4With two frequencies, only two repair shapes work: a lone count-1 letter you can delete entirely, or a single letter whose count is exactly one above the rest.
5You may delete at most one character total — not one per letter.

Use this pattern when

Asked if frequencies can be equalised by removing at most one character
Counts must all match after a single edit, and the edit is a deletion
Small fixed alphabet, so frequency-of-frequencies is tiny (O(1))
You see 'all characters appear the same number of times' as the goal

Choose another pattern when

Allowed to delete more than one character → that's a different (k-deletion) problem
Edit is a replacement, not a deletion → Anagram-style frequency-difference instead
Need to find WHICH character to delete → track the offending letter, not just yes/no
Need the minimum deletions to make valid → count surpluses, don't just test feasibility

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 (alternate framing)
Same frequency-of-frequencies logic under a slightly different problem statement.
Sort Characters By Frequency
Coming soon
Also built on a frequency map, then ordering by count.
Unique Number of Occurrences
Coming soon
Directly asks whether all frequency values are distinct — the same second-level count.
Valid Anagram
Frequency comparison between two strings rather than within one.

Same pattern

←

Sherlock and the Valid String

Continue · Next problem

Two Strings