Skip to main content

Permutation-Difference-Between-Two-String (LeetCode)

Problem Statement:ā€‹

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:

  1. For s = "abc" and t = "bac", the permutation difference of s and t is equal to the sum of:

  2. The absolute difference between the index of the occurrence of "a" in s and the index of the occurrence of "a" in t.

  3. The absolute difference between the index of the occurrence of "b" in s and the index of the occurrence of "b" in `t``.

  4. The absolute difference between the index of the occurrence of "c" in s and the index of the occurrence of "c" in t.

  5. That is, the permutation difference between s and t is equal to |0 - 1| + |2 - 2| + |1 - 0| = 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:ā€‹

Intuitionā€‹

To solve this problem, we need to determine the "distance" between the characters of the string t in terms of their positions in the string s. Specifically, for each character in t, we calculate the absolute difference between its position in s and its position in t, and then sum up these differences.

Approachā€‹

Initialization: Start with a variable sum to accumulate the total difference.

Iteration: Loop through each character in the string t.

Calculation: a. Find the index of the current character in the string s. b. Calculate the absolute difference between this index and the current index in t. c. Add this difference to the sum.

Return Result: After processing all characters, return the accumulated sum.

code:ā€‹

Written by @Ajay-Dhangar
function findPermutationDifference(s: string, t: string): number {
let sum: number = 0;
for (let i = 0; i < t.length; i++) {
sum += Math.abs(s.indexOf(t.charAt(i)) - i);
}
return sum;
}

Complexityā€‹

Time complexity: O(nāˆ—m)O(nāˆ—m) ,where n is the length of t and m is the average length to search in s.

Space complexity: The space complexity is O(1)O(1), since we are only using a constant amount of extra space for the variable sum.

video lecture:ā€‹