Append Animals to Include Preference - codepath/compsci_guides GitHub Wiki

TIP102 Unit 3 Session 1 Advanced (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 input to the problem?
  • A: The input consists of two strings: available representing the animals currently available, and preferred representing the preferred animals.
• Q: What is the output?
  • A: The output is the minimum number of characters that need to be appended to the end of available so that preferred becomes a subsequence of available.
• Q: What is a subsequence?
  • A: A subsequence is a sequence that can be derived from another sequence by deleting some or no characters without changing the order of the remaining characters.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use a two-pointer approach to check how much of the preferred string is already a subsequence of available. The number of characters left in preferred after matching determines how many characters need to be appended.

1. Initialize two pointers `i` and `j` to `0`. Pointer `i` will traverse the `available` list, and pointer `j` will traverse the `preferred` list.
2. Traverse through the `available` string:
   1. If the current character in `available` matches the current character in `preferred`, move both pointers forward.
   2. If the characters do not match, move only the `i` pointer forward.
3. After the loop, if the `j` pointer has not reached the end of the `preferred` list, the remaining characters in `preferred` need to be appended.
4. Return the number of characters to append, which is `len(preferred) - j`.

⚠️ Common Mistakes

• Incorrectly managing the pointers, leading to an incorrect count of characters to append.
• Assuming that all characters in preferred need to be appended if any character doesn't match, rather than only the unmatched portion.
• Not considering cases where preferred is already a subsequence of available.

I-mplement

def append_animals(available, preferred):
    # Step 1: Initialize pointers for both available and preferred lists
    i, j = 0, 0
    len_available = len(available)
    len_preferred = len(preferred)
    
    # Step 2: Traverse the available list to find how much of preferred is a subsequence
    while i < len_available and j < len_preferred:
        if available[i] == preferred[j]:
            j += 1
        i += 1
    
    # Step 3: Calculate the number of characters to append
    # If j has reached the end of preferred, it means all of preferred is a subsequence
    return len_preferred - j

# Example usage
print(append_animals("catsdogs", "cows"))   # Output: 2
print(append_animals("rabbit", "r"))        # Output: 0
print(append_animals("fish", "bird"))       # Output: 4