Remove Letter To Equalize Frequency - Practice Coding Problems

Remove Letter To Equalize Frequency - Problem

You are given a 0-indexed string word, consisting of lowercase English letters. You need to select one index and remove the letter at that index from word so that the frequency of every letter present in word is equal.

Return true if it is possible to remove one letter so that the frequency of all letters in word are equal, and false otherwise.

Note:

The frequency of a letter x is the number of times it occurs in the string.
You must remove exactly one letter and cannot choose to do nothing.

Input & Output

Example 1 — Two Close Frequencies

$ Input: word = "abcc"

› Output: true

💡 Note: Remove one 'c' to get "abc": a:1, b:1, c:1 - all frequencies equal

Example 2 — Cannot Equalize

$ Input: word = "aab"

› Output: false

💡 Note: Remove 'a' → "ab" (a:1,b:1) or remove 'b' → "aa" (a:2) - cannot make equal after any single removal

Example 3 — Single Character Type

$ Input: word = "aaa"

› Output: true

💡 Note: Remove one 'a' to get "aa": only character 'a' with frequency 2

Constraints

1 ≤ word.length ≤ 10⁵
word consists of lowercase English letters
You must remove exactly one character

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

Count frequency of each character in the string

Pattern Recognition

Identify if frequency pattern allows valid removal

Result

Return true if equalization possible, false otherwise

Key Takeaway

🎯 Key Insight: Only specific frequency distribution patterns allow successful equalization after removing exactly one character.

Asked in

G Google 15 a Amazon 12 f Facebook 8

The key insight is recognizing that only specific frequency patterns allow successful equalization after removing one character. The optimal approach uses frequency analysis to identify these patterns in O(n) time rather than testing each removal. Valid patterns include: all equal frequencies, two frequencies differing by 1, or one character with frequency 1 that can be eliminated.

Common Approaches

Approach	Time	Space	Notes
✓ Frequency Analysis - Pattern Recognition	O(n)	O(1)	Count frequencies first, then analyze which patterns allow valid removal
Brute Force - Try Every Removal	O(n²)	O(n)	Try removing each character and check if remaining frequencies are equal

Frequency Analysis - Pattern Recognition — Algorithm Steps

Step 1: Count frequency of each character
Step 2: Analyze frequency distribution
Step 3: Check if any removal creates equal frequencies

Visualization

Tap to expand

Step-by-Step Walkthrough

Count Frequencies

Count each character's frequency

Analyze Pattern

Check frequency distribution patterns

Validate Removal

Determine if removal creates equal frequencies

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool solution(char* word) {
    int freq[26] = {0};
    int n = strlen(word);
    
    for (int i = 0; i < n; i++) {
        freq[word[i] - 'a']++;
    }
    
    int freqCounts[1001] = {0};
    int charCount = 0;
    for (int i = 0; i < 26; i++) {
        if (freq[i] > 0) {
            freqCounts[freq[i]]++;
            charCount++;
        }
    }
    
    int uniqueFreqs[26];
    int uniqueCount = 0;
    for (int i = 1; i <= 1000; i++) {
        if (freqCounts[i] > 0) {
            uniqueFreqs[uniqueCount++] = i;
        }
    }
    
    if (uniqueCount == 1) {
        int f = uniqueFreqs[0];
        if (f == 1) return true;
        if (charCount == 1 || f * charCount - 1 == (f - 1) * charCount) {
            return true;
        }
        return false;
    }
    
    if (uniqueCount == 2) {
        int f1 = uniqueFreqs[0];
        int f2 = uniqueFreqs[1];
        int c1 = freqCounts[f1];
        int c2 = freqCounts[f2];
        
        if (f2 == f1 + 1 && c2 == 1) return true;
        if (f1 == 1 && c1 == 1) return true;
        if (f1 == 1 && f2 * c2 == n - 1) return true;
    }
    
    return false;
}

int main() {
    char word[1001];
    fgets(word, sizeof(word), stdin);
    word[strcspn(word, "\n")] = 0;
    
    bool result = solution(word);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass to count frequencies plus constant time analysis

✓ Linear Growth

Space Complexity

O(1)

Only store frequency counts for at most 26 lowercase letters

✓ Linear Space

32.4K Views

Medium Frequency

~25 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Frequency Analysis - Pattern Recognition — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler