Permutation Difference between Two Strings

Difficulty: Easy | Acceptance: 87.80% | Paid: No Topics: Hash Table, String

You are given two strings s and t such that t is a permutation of s. The permutation difference between s and t is defined as the sum of the absolute differences between the indices of each character in s and t.

Return the permutation difference between s and t.

• Examples
• Constraints
• Hash Map Approach
• Array Index Approach
• Brute Force Approach

Examples

Example 1

Input: s = "abc", t = "bac"
Output: 2
Explanation:
For s = "abc" and t = "bac":
- The index of 'a' in s is 0, and in t is 1. The absolute difference is |0 - 1| = 1.
- The index of 'b' in s is 1, and in t is 0. The absolute difference is |1 - 0| = 1.
- The index of 'c' in s is 2, and in t is 2. The absolute difference is |2 - 2| = 0.
The total permutation difference is 1 + 1 + 0 = 2.

Example 2

Input: s = "abcde", t = "edbac"
Output: 12
Explanation:
For s = "abcde" and t = "edbac":
- The index of 'a' in s is 0, and in t is 2. The absolute difference is |0 - 2| = 2.
- The index of 'b' in s is 1, and in t is 3. The absolute difference is |1 - 3| = 2.
- The index of 'c' in s is 2, and in t is 4. The absolute difference is |2 - 4| = 2.
- The index of 'd' in s is 3, and in t is 1. The absolute difference is |3 - 1| = 2.
- The index of 'e' in s is 4, and in t is 0. The absolute difference is |4 - 0| = 4.
The total permutation difference is 2 + 2 + 2 + 2 + 4 = 12.

Constraints

1 <= s.length <= 26
s.length == t.length
s and t consist of lowercase English letters.
t is a permutation of s.

Hash Map Approach

Intuition Store the index of each character in string s using a hash map, then iterate through t to calculate the absolute difference between each character’s position in both strings.

Steps

• Create a hash map to store each character’s index in string s
• Iterate through string t and for each character, find its index in s using the hash map
• Calculate the absolute difference between the current index in t and the index in s
• Sum all these differences and return the result

class Solution:
    def findPermutationDifference(self, s: str, t: str) -> int:
        index_map = {}
        for i, char in enumerate(s):
            index_map[char] = i
        
        total_diff = 0
        for i, char in enumerate(t):
            total_diff += abs(i - index_map[char])
        
        return total_diff

Complexity

• Time: O(n) where n is the length of the strings
• Space: O(n) for the hash map
• Notes: Efficient lookup with hash map, optimal for general character sets

Array Index Approach

Intuition Since the strings consist of lowercase English letters only, we can use a fixed-size array of 26 elements to store indices, avoiding hash map overhead.

Steps

• Create an array of size 26 initialized to -1
• Store the index of each character in string s using character code offset
• Iterate through string t and calculate the absolute difference using the array lookup
• Sum all differences and return the result

class Solution:
    def findPermutationDifference(self, s: str, t: str) -> int:
        index_arr = [-1] * 26
        for i, char in enumerate(s):
            index_arr[ord(char) - ord('a')] = i
        
        total_diff = 0
        for i, char in enumerate(t):
            total_diff += abs(i - index_arr[ord(char) - ord('a')])
        
        return total_diff

Complexity

• Time: O(n) where n is the length of the strings
• Space: O(1) since the array size is fixed at 26
• Notes: More memory efficient than hash map for lowercase letters only

Brute Force Approach

Intuition For each character in t, search for its position in s and calculate the difference directly without any preprocessing.

Steps

• Initialize total difference to 0
• For each character in string t at index i
• Find the index of that character in string s
• Add the absolute difference between i and the found index to total
• Return the total difference

class Solution:
    def findPermutationDifference(self, s: str, t: str) -> int:
        total_diff = 0
        for i, char in enumerate(t):
            total_diff += abs(i - s.index(char))
        return total_diff

Complexity

• Time: O(n²) where n is the length of the strings
• Space: O(1) no additional space used
• Notes: Simple but less efficient, suitable for small input sizes