3146. Permutation Difference between Two Strings
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"
ins
and the index of the occurrence of"a"
int
. - The absolute difference between the index of the occurrence of
"b"
ins
and the index of the occurrence of"b"
int
. - The absolute difference between the index of the occurrence of
"c"
ins
and the index of the occurrence of"c"
int
.
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 ofs
.s
consists only of lowercase English letters.
Solutions
Solution 1: Hash Table or Array
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 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 10 |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|