Stage Arrangement Difference Between Two Performances - 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 stage arrangement difference between two strings s and t that represent stage arrangements of performers, where t is a permutation of s.

• Q: What are the inputs?

  • A: Two strings s and t, both containing the same characters with t being a permutation of s.

• Q: What are the outputs?

  • A: An integer representing the stage arrangement difference.

• Q: Are there any constraints on the strings?

  • A: Every performer occurs at most once in s and t, and t is a permutation of s.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Map each character in s to its index and then calculate the sum of the absolute differences between the indices in s and t.

1) Create a dictionary `index_map` to map each performer in `s` to their index.
2) Iterate through each character in `s` and populate `index_map`.
3) Initialize a variable `difference` to 0.
4) Iterate through each character in `t`.
   - For each character, calculate the absolute difference between its index in `t` and its index in `s` using `index_map`.
   - Add the absolute difference to `difference`.
5) Return the value of `difference`.

⚠️ Common Mistakes

• Ensure that the indices are correctly mapped and differences are accurately calculated.
• Handle cases where the strings are identical, resulting in a difference of 0.

I-mplement

def find_stage_arrangement_difference(s, t):
    # Step 1: Create a dictionary to map each performer in s to their index
    index_map = {}
    for i in range(len(s)):
        index_map[s[i]] = i
    
    # Step 2: Calculate the stage arrangement difference
    difference = 0
    for j in range(len(t)):
        performer = t[j]
        difference += abs(index_map[performer] - j)
    
    return difference