#3146

Easy

LeetCode Problem Workspace

Permutation Difference between Two Strings

Compute the total index difference between two strings by mapping characters and summing their positional distances efficiently.

hash table string

Problem Statement

Given two strings s and t, where t is a permutation of s and each character occurs at most once, compute the sum of the absolute differences between the indices of each character in s and its index in t. Every character is lowercase, and strings are up to 26 characters long.

Return the total permutation difference as an integer. For example, if s = 'abc' and t = 'bac', calculate |0 - 1| + |1 - 0| + |2 - 2| = 2. Ensure your solution efficiently maps characters to indices using a hash table to handle the index lookups.

Examples

Example 1

Input: s = "abc", t = "bac"

Output: 2

For s = "abc" and t = "bac" , the permutation difference of s and t is equal to the sum of: That is, the permutation difference between s and t is equal to |0 - 1| + |1 - 0| + |2 - 2| = 2 .

Example 2

Input: s = "abcde", t = "edbac"

Output: 12

The permutation difference between s and t is equal to |0 - 3| + |1 - 2| + |2 - 4| + |3 - 1| + |4 - 0| = 12 .

Constraints

1 <= s.length <= 26
Each character occurs at most once in s.
t is a permutation of s.
s consists only of lowercase English letters.

Solution Approach

Map Characters of s to Indices

Create a hash table where each character in s is a key and its index is the value. This allows O(1) lookup of any character's original position in s.

Iterate Through t and Sum Differences

For each character in t, find its index in s using the hash table and compute the absolute difference between positions. Sum these differences to get the permutation difference.

Return the Total Difference

After processing all characters, return the accumulated sum. This ensures the algorithm runs in linear time relative to the string length, avoiding quadratic index searches.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) for building the hash table and iterating through t, where n is the length of the strings. Space complexity is O(n) to store character-to-index mappings.

What Interviewers Usually Probe

Check if candidates immediately use a mapping to avoid nested loops.
Listen for mentions of absolute differences and character positions.
Observe whether they consider constraints like single occurrence of characters.

Common Pitfalls or Variants

Common pitfalls

Using nested loops to search indices instead of a hash table, causing O(n^2) time.
Forgetting that t is always a permutation of s, leading to unnecessary checks.
Incorrectly summing differences without taking absolute values.

Follow-up variants

Allow characters to repeat and calculate permutation difference accordingly.
Return an array of individual differences for each character instead of the sum.
Compute permutation difference for multiple pairs of strings in batch efficiently.

FAQ

What is the main pattern in Permutation Difference between Two Strings?

The key pattern is Hash Table plus String, mapping each character to its index for efficient difference computation.

Can the strings contain repeated characters?

In the base problem, each character occurs at most once. Variants may allow repeats, changing the mapping strategy.

What is the time complexity of the optimal solution?

Using a hash table to store indices and iterating over t gives O(n) time complexity.

Do I need to sort the strings before computing differences?

No, since t is already a permutation of s, sorting is unnecessary and adds extra complexity.

How do I handle large strings efficiently?

Even though strings are small here, for larger inputs, always use a hash table to avoid repeated index searches.

terminal

Solution

Solution 1: Hash Table or Array

We can use a hash table or an array of length $26$, denoted as $\textit{d}$, to store the positions of each character in the string $\textit{s}$.

1

2

3

4

class Solution:
    def findPermutationDifference(self, s: str, t: str) -> int:
        d = {c: i for i, c in enumerate(s)}
        return sum(abs(d[c] - i) for i, c in enumerate(t))

Continue Practicing

#3144 minimum substring partition of equal character frequency #3143 maximum points inside the square #3138 minimum length of anagram concatenation