Signal Pairs - codepath/compsci_guides GitHub Wiki

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

U-nderstand

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

• Q: What is the problem asking for?

  • A: The problem asks to return the maximum number of pairs that can be formed from an array of distinct strings where each string can be paired with its reversed version from the array.

• Q: What are the inputs?

  • A: A 0-indexed array signals consisting of distinct strings.

• Q: What are the outputs?

  • A: An integer representing the maximum number of pairs that can be formed.

• Q: Are there any constraints on the values in the array?

  • A: The strings are distinct, and each string can belong to at most one pair.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use a dictionary to count occurrences of each string and its reverse to form pairs.

1. Initialize an empty dictionary `signal_count` to store the frequency of each string.
2. Initialize a variable `pair_count` to 0 to count the number of pairs.
3. Iterate through the `signals` array.
   - For each string, calculate its reverse.
   - If the reverse string exists in `signal_count` with a count greater than 0, form a pair, decrement the count, and increment `pair_count`.
   - If the reverse string does not exist or its count is 0, add the string to `signal_count` or increment its count if it already exists.
4. Return the value of `pair_count`.

I-mplement

def max_number_of_string_pairs(signals):
    signal_count = {}
    pair_count = 0
    
    for signal in signals:
        reverse_signal = signal[::-1]
        if reverse_signal in signal_count and signal_count[reverse_signal] > 0:
            pair_count += 1
            signal_count[reverse_signal] -= 1
        else:
            if signal in signal_count:
                signal_count[signal] += 1
            else:
                signal_count[signal] = 1
    
    return pair_count