3146. Permutation Difference between Two Strings LeetCode Solution
In this guide, you will get 3146. Permutation Difference between Two Strings LeetCode Solution with the best time and space complexity. The solution to Permutation Difference between Two Strings problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Permutation Difference between Two Strings
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.
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(26) = O(1)
3146. Permutation Difference between Two Strings LeetCode Solution in C++
class Solution {
public:
int findPermutationDifference(string s, string t) {
int ans = 0;
vector<int> indices(26);
for (int i = 0; i < s.length(); ++i)
indices[s[i] - 'a'] = i;
for (int i = 0; i < t.length(); ++i)
ans += abs(indices[t[i] - 'a'] - i);
return ans;
}
}; /* code provided by PROGIEZ */
3146. Permutation Difference between Two Strings LeetCode Solution in Java
class Solution {
public int findPermutationDifference(String s, String t) {
int ans = 0;
int[] indices = new int[26];
for (int i = 0; i < s.length(); ++i)
indices[s.charAt(i) - 'a'] = i;
for (int i = 0; i < t.length(); ++i)
ans += Math.abs(indices[t.charAt(i) - 'a'] - i);
return ans;
}
} // code provided by PROGIEZ
3146. Permutation Difference between Two Strings LeetCode Solution in Python
class Solution:
def findPermutationDifference(self, s: str, t: str) -> int:
indices = {c: i for i, c in enumerate(s)}
return sum([abs(indices[c] - i) for i, c in enumerate(t)]) # code by PROGIEZ
