# Permutation Difference between Two Strings
**Difficulty:** EASY
[External](https://leetcode.com/problems/permutation-difference-between-two-strings)
Canonical: https://scaleengineer.com/dsa/problems/permutation-difference-between-two-strings
**Data structures:** Hash Table, String
**Companies:** [Accenture](https://scaleengineer.com/companies/accenture)
---
## Problem
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:

* The absolute difference between the index of the occurrence of `"a"` in `s` and the index of the occurrence of `"a"` in `t`.
* The absolute difference between the index of the occurrence of `"b"` in `s` and the index of the occurrence of `"b"` in `t`.
* The absolute difference between the index of the occurrence of `"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 <= 26`
* Each character occurs at most once in `s`.
* `t` is a permutation of `s`.
* `s` consists only of lowercase English letters.

# Approaches
## Brute Force with Nested Loops
This approach directly translates the problem definition into code. We iterate through each character of the first string `s`. For each character, we then perform a search in the second string `t` to find the same character and its index. The absolute difference of the indices is then added to a running total.
**Time:** O(n^2), where n is the length of the strings. The nested loops result in a quadratic time complexity, as for each of the n characters in `s`, we might have to scan all n characters of `t` in the worst case. · **Space:** O(1). No extra space proportional to the input size is used. We only use a few variables for the sum and loop counters.
**Pros:** Very simple to conceptualize and implement.; Does not require any auxiliary data structures.
**Cons:** Inefficient for longer strings due to the quadratic time complexity.; The performance degrades quickly as the string length increases.
### Explanation
The algorithm works as follows:
1.  Initialize a variable `difference` to 0. This will store the sum of the absolute index differences.
2.  Iterate through the string `s` with an index `i` from 0 to `s.length() - 1`.
3.  For each character `s.charAt(i)`, start a nested loop to iterate through the string `t` with an index `j` from 0 to `t.length() - 1`.
4.  Inside the inner loop, check if the character from `s` matches the character from `t` (i.e., `s.charAt(i) == t.charAt(j)`).
5.  If they match, calculate the absolute difference of their indices: `Math.abs(i - j)`.
6.  Add this difference to the `difference` variable.
7.  Since each character is unique, we can break the inner loop once a match is found and proceed to the next character in `s`.
8.  After the outer loop completes, return the total `difference`.

```java
class Solution {
    public int findPermutationDifference(String s, String t) {
        int n = s.length();
        int totalDifference = 0;
        for (int i = 0; i < n; i++) {
            char charS = s.charAt(i);
            for (int j = 0; j < n; j++) {
                if (charS == t.charAt(j)) {
                    totalDifference += Math.abs(i - j);
                    break; // Character found, break inner loop
                }
            }
        }
        return totalDifference;
    }
}
```
### Algorithm
*   Initialize a variable `difference` to 0.
*   Iterate through the string `s` with an index `i` from 0 to `s.length() - 1`.
*   For each character `s.charAt(i)`, start a nested loop to iterate through the string `t` with an index `j` from 0 to `t.length() - 1`.
*   Inside the inner loop, if `s.charAt(i)` matches `t.charAt(j)`, calculate the absolute difference of their indices, `|i - j|`.
*   Add this difference to the `difference` variable.
*   Break the inner loop since characters are unique.
*   After the outer loop completes, return the total `difference`.

## Optimized Approach using an Array as a Map
This approach improves upon the brute-force method by optimizing the search for character indices. We can pre-process one of the strings (e.g., `t`) to store the index of each character in a map-like data structure. Since the characters are limited to lowercase English letters, a simple array of size 26 can serve as a highly efficient direct-access map. This allows us to find the index of any character in `t` in constant time.
**Time:** O(n), where n is the length of the strings. The algorithm consists of two independent loops, each running `n` times. The first loop populates the index map, and the second calculates the sum. This results in a total time complexity of O(n) + O(n) = O(n). · **Space:** O(1). We use an integer array of size 26 to store character indices. Since the size of this array is constant and does not depend on the input string length `n`, the space complexity is considered constant.
**Pros:** Highly efficient with linear time complexity, making it suitable for larger inputs.; Optimal solution for the given problem constraints.
**Cons:** Requires a small amount of extra space for the mapping array.
### Explanation
The optimized algorithm proceeds in two main steps:
1.  **Preprocessing:**
    *   Create an integer array, let's call it `t_indices`, of size 26. This array will map each lowercase letter to its index in string `t`.
    *   Iterate through the string `t` from `i = 0` to `t.length() - 1`.
    *   For each character `c = t.charAt(i)`, store its index `i` in the array at the position corresponding to that character: `t_indices[c - 'a'] = i`.

2.  **Calculation:**
    *   Initialize a variable `difference` to 0.
    *   Iterate through the string `s` with an index `i` from 0 to `s.length() - 1`.
    *   For each character `c = s.charAt(i)`, its index in `s` is `i`.
    *   Retrieve its index in `t` directly from our precomputed array: `j = t_indices[c - 'a']`.
    *   Calculate the absolute difference `Math.abs(i - j)` and add it to the `difference` variable.
3.  After iterating through `s`, return the total `difference`.

```java
class Solution {
    public int findPermutationDifference(String s, String t) {
        int[] t_indices = new int[26];
        // Pre-process string t to store character indices
        for (int i = 0; i < t.length(); i++) {
            t_indices[t.charAt(i) - 'a'] = i;
        }
        
        int totalDifference = 0;
        // Iterate through string s to calculate the difference
        for (int i = 0; i < s.length(); i++) {
            char charS = s.charAt(i);
            int indexInS = i;
            int indexInT = t_indices[charS - 'a'];
            totalDifference += Math.abs(indexInS - indexInT);
        }
        
        return totalDifference;
    }
}
```
### Algorithm
*   Create an integer array `t_indices` of size 26.
*   Iterate through string `t` and populate `t_indices` where `t_indices[char - 'a']` stores the index of `char` in `t`.
*   Initialize `totalDifference = 0`.
*   Iterate through string `s` with index `i`.
*   For each character `c = s.charAt(i)`, get its index in `t` from `t_indices[c - 'a']`.
*   Add `|i - t_indices[c - 'a']|` to `totalDifference`.
*   Return `totalDifference`.

# Solutions
### CSharp

```csharp
public class Solution {
    public int FindPermutationDifference(string s, string t) {
        int[] d = new int[26];
        int n = s.Length;
        for (int i = 0; i < n; ++i) {
            d[s[i] - 'a'] = i;
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans += Math.Abs(d[t[i] - 'a'] - i);
        }
        return ans;
    }
}
```

### Java

```java
class Solution {
public
  int findPermutationDifference(String s, String t) {
    int[] d = new int[26];
    int n = s.length();
    for (int i = 0; i < n; ++i) {
      d[s.charAt(i) - 'a'] = i;
    }
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      ans += Math.abs(d[t.charAt(i) - 'a'] - i);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int findPermutationDifference(string s, string t) {
    int d[26]{};
    int n = s.size();
    for (int i = 0; i < n; ++i) {
      d[s[i] - 'a'] = i;
    }
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      ans += abs(d[t[i] - 'a'] - i);
    }
    return ans;
  }
};

```

### Python

```python
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))

```