Valid Frequency String Check - String Coding Interview

Question

## Problem

A string is "frequency-valid" if you can remove at most one character from it such that all remaining characters appear the same number of times.

```python
def is_frequency_valid(s: str) -> bool:
    ...
```

**Examples:**
```
"aabbc"   -> True   # remove one 'c': "aabb" all chars appear 2 times
"aabbccc" -> True   # remove one 'c': "aabbcc" all appear 2 times
"aabbccdd"-> True   # already valid (all appear 2 times, 0 removals)
"aaabbbcc" -> False # no single removal balances it
"aabc"    -> True   # remove one 'a': "abc" all appear 1 time
```

## Approach

Count character frequencies, then count frequency-of-frequencies. Valid states after one removal:
1. All chars same freq (0 removals needed).
2. One char with freq 1 and all others same freq.
3. One char with freq `f` where `f - 1` equals all others' freq.
4. One char with the max freq where max freq = min freq + 1 and only one char has that max.

## Follow-ups
- Can you enumerate all edge cases systematically? (e.g., single character string, all same character)
- Extend to "at most k removals" -- how does the solution change?
- What is the time and space complexity?

Valid Frequency String Check - String Coding Interview

Question Details

Full Details

Topics

More from Bloomberg