3146. Permutation Difference between Two Strings

EasyHash TableString

Problem Description

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.

Intuition

To solve this problem, the key idea is to track the index of each character in the string s. We can do this efficiently using a dictionary. By mapping each character of s to its position, we can quickly determine where each character is supposed to be according to the string s.

Once we have this mapping, the next step is to iterate over the string t, which is a permutation of s. For each character in t, we calculate the absolute difference between its index in t and its expected index from our dictionary of s.

Finally, we sum up all these absolute differences. This sum represents the permutation difference between the strings s and t.

This approach leverages the properties of permutations and the efficiency of dictionary lookups to compute the solution with minimal computational complexity.

Solution Approach

The solution involves a simple yet effective use of a dictionary to track indices of characters in string s. Here's a step-by-step breakdown of the approach:

Store Indices of Characters:
- Create a dictionary d where each character in the string s is a key and its index in s is the value. This is done using a dictionary comprehension:
```
d = {c: i for i, c in enumerate(s)}
```
This allows us to map each character to its corresponding position in s.
Calculate Permutation Difference:
- Iterate over the string t using enumerate, which provides both the index and the character. For each character c at index i in t, find its index in the dictionary d (which gives its original index in s). Compute the absolute difference between the two indices.
- Sum all these absolute differences to compute the permutation difference. This is achieved in a single line using a generator expression inside a sum function:
```
return sum(abs(d[c] - i) for i, c in enumerate(t))
```

This solution efficiently computes the permutation difference by utilizing the direct index lookups provided by the dictionary, resulting in a time complexity of O(n), where n is the length of the strings s and t.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's take a small example to illustrate the solution approach:

Suppose we have the strings s = "abc" and t = "bca".

Step 1: Store Indices of Characters

First, we create a dictionary d to map each character in s to its index:

a is at index 0 in s
b is at index 1 in s
c is at index 2 in s

Thus, our dictionary d becomes:

d = {'a': 0, 'b': 1, 'c': 2}

Step 2: Calculate Permutation Difference

Next, we iterate over string t to calculate the permutation difference. We keep track of the absolute difference between the index in t and the index in s (using dictionary d) for each character.

For t[0] = 'b':
- d['b'] is 1, and its index in t is 0.
- The absolute difference is abs(1 - 0) = 1.
For t[1] = 'c':
- d['c'] is 2, and its index in t is 1.
- The absolute difference is abs(2 - 1) = 1.
For t[2] = 'a':
- d['a'] is 0, and its index in t is 2.
- The absolute difference is abs(0 - 2) = 2.

Finally, we sum all these absolute differences: 1 + 1 + 2 = 4.

Thus, the permutation difference between the strings s = "abc" and t = "bca" is 4.

Solution Implementation

1class Solution:
2    def findPermutationDifference(self, s: str, t: str) -> int:
3        # Create a dictionary to map characters in 's' to their indices
4        index_map = {char: index for index, char in enumerate(s)}
5      
6        # Calculate the sum of absolute differences between the index in 's' and 't'
7        total_difference = sum(abs(index_map[char] - index) for index, char in enumerate(t))
8      
9        return total_difference
10

1class Solution {
2    // Compute the permutation difference between two strings s and t.
3    public int findPermutationDifference(String s, String t) {
4        // Array to store positions of each character in string s.
5        int[] positions = new int[26]; // Assuming all characters are lowercase English letters.
6        int length = s.length(); // Length of the strings s and t.
7      
8        // Populate the positions array with the index of each character in string s.
9        for (int i = 0; i < length; ++i) {
10            positions[s.charAt(i) - 'a'] = i; // Assign the index of character in s to its position.
11        }
12      
13        int difference = 0; // Initialize the difference counter.
14      
15        // Calculate the sum of absolute differences between positions in s and indices in t.
16        for (int i = 0; i < length; ++i) {
17            difference += Math.abs(positions[t.charAt(i) - 'a'] - i); // Add the absolute difference of positions to the running total.
18        }
19      
20        return difference; // Return the total computed difference.
21    }
22}
23

1class Solution {
2public:
3    int findPermutationDifference(std::string s, std::string t) {
4        // Array to store the position/index of each character in string 's'.
5        int position[26] = {}; 
6      
7        // Get the size of the string 's'.
8        int n = s.size(); 
9      
10        // Populate 'position' array with indices of each character in 's'.
11        for (int i = 0; i < n; ++i) {
12            position[s[i] - 'a'] = i;
13        }
14      
15        // Variable to store the total permutation difference.
16        int permutation_difference = 0;
17      
18        // Calculate the difference by iterating over string 't'.
19        for (int i = 0; i < n; ++i) {
20            // Add the absolute difference of current position and expected position.
21            permutation_difference += std::abs(position[t[i] - 'a'] - i);
22        }
23      
24        // Return the total permutation difference.
25        return permutation_difference;
26    }
27};
28

1// Function to calculate the permutation difference between strings s and t
2function findPermutationDifference(s: string, t: string): number {
3    // Array 'd' to store the position index of each character in string 's'
4    const d: number[] = Array(26).fill(0);
5
6    // Length of the strings (assuming both have the same length)
7    const n = s.length;
8
9    // Populate 'd' with indices of characters from string 's'
10    for (let i = 0; i < n; ++i) {
11        // Calculate the position index for character in 's', assuming 'a' is at index 0
12        d[s.charCodeAt(i) - 97] = i;
13    }
14
15    // Initialize answer variable to accumulate the positional differences
16    let ans = 0;
17
18    // Calculate the total permutation difference for string 't' compared to 's'
19    for (let i = 0; i < n; ++i) {
20        // Accumulate the absolute difference between the expected and actual position
21        ans += Math.abs(d[t.charCodeAt(i) - 97] - i);
22    }
23
24    // Return the computed permutation difference
25    return ans;
26}
27

Time and Space Complexity

The time complexity of the code is O(n), where n is the length of the string s. This results from creating a dictionary d that involves iterating over the string s once to populate it, which is O(n), and then summing up the absolute differences, iterating over the string t, which is another O(n). Therefore, the total time complexity remains O(n).

The space complexity is O(|Σ|), where Σ is the character set of the string s. Since we are using a dictionary to store the characters and their indices from s, the space used is proportional to the number of unique characters in s. If lowercase English letters are used, |Σ| is at most 26, so the space complexity is O(26), which simplifies to O(1) given the small constant size of the alphabet.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Which technique can we use to find the middle of a linked list?

Fast-slow pointers

Two pointers moving in opposite direction

Binary search

Depth first search

I don’t know