You are given two strings s and t such that every character occurs at most once in s and t is a permutation of s.
The permutation difference between s and t is defined as the sum of the absolute difference between the index of the occurrence of each character in s and the index of the occurrence of the same character in t.
Return the permutation difference between s and t.
Example 1:
Input: s = "abc", t = "bac"
Output: 2
Explanation:
For s = "abc" and t = "bac", the permutation difference of s and t is equal to the sum of:
"a" in s and the index of the occurrence of "a" in t."b" in s and the index of the occurrence of "b" in t."c" in s and the index of the occurrence of "c" in t.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
Explanation: 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 <= 26s.t is a permutation of s.s consists only of lowercase English letters.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.
This approach leverages the ability to find the index of each character in a string efficiently. For each character in the string s, we find its index in both s and t and accumulate the absolute difference of these indices to compute the permutation difference.
We iterate over each character in string s. For each character, we calculate the index in string s and t. The absolute difference between these indices is added to the total sum, which is the permutation difference.
Time Complexity: O(n^2), where n is the length of the string. This is because for each character, we perform an index lookup which is O(n).
Space Complexity: O(1), as we are only using a few variables to store intermediate results.
This approach optimizes index retrieval by constructing a map for each character's index in both strings before calculating differences. The process is thus streamlined, with quick look-ups during the difference calculation phase.
We first create mapping dictionaries for the indices of characters in both s and t. These mappings allow O(1) retrieval of character positions, leading to efficient computation of the permutation difference.
Time Complexity: O(n), since each map is constructed in O(n) time and each index retrieval is O(1).
Space Complexity: O(n), because of the additional data structures for mapping.
| Approach | Complexity |
|---|---|
| Using Index Lookup | Time Complexity: O(n^2), where n is the length of the string. This is because for each character, we perform an index lookup which is O(n). |
| Mapping with a Dictionary | Time Complexity: O(n), since each map is constructed in O(n) time and each index retrieval is O(1). |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Index Lookup with Fixed Array | O(n) | O(1) | Best when characters are limited (e.g., lowercase letters). Fastest and most memory‑efficient. |
| Mapping with Dictionary | O(n) | O(n) | General solution when character set may vary or constraints are unknown. |
3146. Permutation Difference between Two Strings | Permutation | EASY | LeetCode | String | Map • Leet's Code • 1,073 views views
Watch 8 more video solutions →Practice Permutation Difference between Two Strings with our built-in code editor and test cases.
Practice on FleetCode