Permutation Difference between Two Strings

Permutation Difference between Two Strings

What is this problem about?

The Permutation Difference between Two Strings problem gives you two strings s and t that are permutations of each other. Compute the absolute difference sum: for each character c, |index_in_s(c) - index_in_t(c)|. This easy coding problem tests hash map index tracking. The hash table and string interview pattern is demonstrated.

Why is this asked in interviews?

Microsoft, Accenture, and Google ask this as a quick implementation problem testing index mapping with hash maps. It validates basic character tracking and absolute difference computation.

Algorithmic pattern used

Hash map for character positions + sum of differences. Build pos_s[c] = index of c in s. Build pos_t[c] = index of c in t. Sum |pos_s[c] - pos_t[c]| for each character c.

Example explanation

s="abc", t="bac". pos_s: {a:0,b:1,c:2}. pos_t: {b:0,a:1,c:2}.

• a: |0-1|=1. b: |1-0|=1. c: |2-2|=0. Sum = 2.

Common mistakes candidates make

• Using the same map for both strings (overwriting positions).
• Not handling case sensitivity.
• Iterating characters in the wrong order.
• Forgetting absolute value.

Interview preparation tip

Character position mapping problems are straightforward hash map exercises. Always build separate maps for each string. The pattern pos_s[c] = index is O(n) to build and O(1) per lookup. Practice similar problems: "minimum swaps to convert s to t," "position difference with sorting." Clean hash map operations are the foundation for most string manipulation problems.