Permutation Difference between Two Strings - Video Solutions

Problem Overview: You get two strings s and t that are permutations of the same characters. For every character, compute the absolute difference between its index in s and its index in t, then sum all those differences. The task is essentially comparing the position of each character across two permutations.

Approach 1: Using Index Lookup (O(n) time, O(1) space)

Store the index of every character from s using a fixed array or direct index lookup. Since characters are lowercase English letters, you can use a size‑26 array where pos[c - 'a'] stores the position of that character in s. Iterate through t, look up the stored index from s, and add abs(i - pos[c]) to the running total. Each lookup and update is constant time, so the entire pass runs in linear time.

This approach is efficient because it replaces repeated searches with direct indexing. Instead of scanning the string for every character, the algorithm performs constant-time lookups. The space cost stays constant since the alphabet size is fixed. This method is common when solving Hash Table and String problems involving character positions.

Approach 2: Mapping with a Dictionary (O(n) time, O(n) space)

Create a dictionary (hash map) that maps each character in s to its index. Traverse s once and store map[char] = index. Then iterate through t, retrieve the stored index for each character, and accumulate the absolute difference between indices.

The dictionary provides average O(1) lookup time, keeping the overall complexity linear. This version is more flexible than the array lookup approach because it works even if the character set changes or includes non‑alphabet characters. The tradeoff is additional memory proportional to the number of distinct characters.

Both approaches rely on the same insight: the permutation difference only depends on where each character appears in the two strings. Instead of comparing entire strings repeatedly, store positions once and reuse them through constant‑time lookups.

Recommended for interviews: The index lookup approach is usually preferred. It demonstrates awareness of character constraints and reduces memory to O(1). Interviewers still accept the dictionary solution since it clearly applies the hash table pattern and keeps the algorithm clean and readable. Showing the dictionary version first and then optimizing to a fixed array highlights strong problem‑solving instincts.