Skip to content

3146. Permutation Difference between Two Strings

SourceWeekly Contest 397 Q1DifficultyEasyRating1152

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.

 

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.

Solutions

Solution 1: Hash Table or Array

Thinking

The difference sums absolute index gaps of each letter in \(s\) and \(t\). Searching the other string per letter is quadratic.

Both strings are permutations, so letter-to-index is a bijection and one map suffices.

Store positions of \(s\), then walk \(t\) and add \(|d[c]-i|\).

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}\).

Then, we traverse the string \(\textit{t}\) and calculate the sum of the absolute differences between the positions of each character in the string \(\textit{t}\) and the positions in the string \(\textit{s}\).

The time complexity is \(O(n)\), where \(n\) is the length of the string \(\textit{s}\). The space complexity is \(O(|\Sigma|)\), where \(\Sigma\) is the character set. Here, it is lowercase English letters, so \(|\Sigma| \leq 26\).

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
func findPermutationDifference(s string, t string) (ans int) {
    d := [26]int{}
    for i, c := range s {
        d[c-'a'] = i
    }
    for i, c := range t {
        ans += max(d[c-'a']-i, i-d[c-'a'])
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
function findPermutationDifference(s: string, t: string): number {
    const d: number[] = Array(26).fill(0);
    const n = s.length;
    for (let i = 0; i < n; ++i) {
        d[s.charCodeAt(i) - 97] = i;
    }
    let ans = 0;
    for (let i = 0; i < n; ++i) {
        ans += Math.abs(d[t.charCodeAt(i) - 97] - i);
    }
    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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;
    }
}

Comments