Booby Trap - codepath/compsci_guides GitHub Wiki

Unit 2 Session 1 (Click for link to problem statements)

Problem Highlights

💡 Difficulty: Medium
⏰ Time to complete: 15-20 mins
🛠️ Topics: Strings, Frequency Dictionaries, Conditional Logic

U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

Q: What does it mean for the code to be balanced?
- A: The code is balanced if, after removing exactly one letter, all remaining letters have the same frequency.
Q: Can the string be empty or consist of only one letter?
- A: No, the string must contain at least two letters since the task requires removing exactly one letter.
Q: What if all letters already have the same frequency?
- A: If all letters have the same frequency, removing one letter should make the frequencies still equal, so the function should return True.
Q: How do we handle cases with different frequencies?
- A: We need to check if removing one letter can equalize the frequencies of the remaining letters.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: We need to determine if we can remove exactly one letter from the string so that the remaining letters have equal frequencies. To achieve this, we'll use frequency dictionaries to track how often each letter appears and how often each frequency occurs.

1) Create a frequency dictionary (`freq_dict`) to count how often each character appears in the code.
2) Create a frequency of frequencies dictionary (`frequency_count`) to count how often each frequency appears in `freq_dict`.
3) Determine the number of unique frequencies.
4) If there are three or more unique frequencies, it's impossible to balance the code by removing just one letter, so return `False`.
5) If there's only one unique frequency:
    - If all characters are the same or have a frequency of 1, return `True`.
6) If there are exactly two unique frequencies, check if removing one letter can balance the remaining letters:
    - If one frequency is 1 and it occurs exactly once, return `True`.
    - If the difference between the two frequencies is 1 and the higher frequency occurs exactly once, return `True`.
7) If none of the conditions are met, return `False`.

⚠️ Common Mistakes

Forgetting to account for edge cases, such as when all characters have the same frequency or when only one character can be removed to achieve balance.
Misinterpreting the frequency dictionary or incorrectly comparing the frequencies.

I-mplement

def is_balanced(code):
    # Step 1: Create a frequency dictionary for characters
    # freq_dict will store the frequency of each character in the string 'code'
    freq_dict = {}
    for char in code:
        if char in freq_dict:
            freq_dict[char] += 1
        else:
            freq_dict[char] = 1

    # Step 2: Create a frequency of frequencies dictionary
    # frequency_count will store how many times each frequency occurs
    frequency_count = {}
    for val in freq_dict.values():
        if val in frequency_count:
            frequency_count[val] += 1
        else:
            frequency_count[val] = 1

    # dict_length stores the number of unique frequencies
    dict_length = len(frequency_count)
    
    # If there are 3 or more different frequencies, it's impossible to balance by removing one character
    if dict_length >= 3:
        return False

    # If there's only one unique frequency
    if dict_length == 1:
        # Check if all characters are the same or if the frequency is 1, which is a special case
        if len(freq_dict.keys()) == 1:
            return True
        # If all characters have the same frequency, we can remove one to potentially balance the string
        return list(frequency_count.keys())[0] == 1

    # If there are exactly two unique frequencies
    for val, freq in frequency_count.items():
        # Check if one of the frequencies is 1 and it occurs exactly once, allowing removal to balance the string
        if val == 1 and freq == 1:
            return True

    # Extract the two unique frequencies for further checks
    values = list(frequency_count.keys())
    
    # Check if the difference between the two frequencies is 1 and the higher frequency occurs exactly once
    if values[0] - values[1] == 1 and frequency_count[values[0]] == 1:
        return True

    # Check the reverse of the above condition
    if values[1] - values[0] == 1 and frequency_count[values[1]] == 1:
        return True

    # If none of the conditions are met, it's impossible to balance by removing one character
    return False