Permutation Difference between Two Strings
EasyPrompt
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"insand the index of the occurrence of"a"int. - The absolute difference between the index of the occurrence of
"b"insand the index of the occurrence of"b"int. - The absolute difference between the index of the occurrence of
"c"insand 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. tis a permutation ofs.sconsists only of lowercase English letters.
Approaches
2 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Initialize a variable
differenceto 0. - Iterate through the string
swith an indexifrom 0 tos.length() - 1. - For each character
s.charAt(i), start a nested loop to iterate through the stringtwith an indexjfrom 0 tot.length() - 1. - Inside the inner loop, if
s.charAt(i)matchest.charAt(j), calculate the absolute difference of their indices,|i - j|. - Add this difference to the
differencevariable. - Break the inner loop since characters are unique.
- After the outer loop completes, return the total
difference.
Walkthrough
The algorithm works as follows:
- Initialize a variable
differenceto 0. This will store the sum of the absolute index differences. - Iterate through the string
swith an indexifrom 0 tos.length() - 1. - For each character
s.charAt(i), start a nested loop to iterate through the stringtwith an indexjfrom 0 tot.length() - 1. - Inside the inner loop, check if the character from
smatches the character fromt(i.e.,s.charAt(i) == t.charAt(j)). - If they match, calculate the absolute difference of their indices:
Math.abs(i - j). - Add this difference to the
differencevariable. - Since each character is unique, we can break the inner loop once a match is found and proceed to the next character in
s. - After the outer loop completes, return the total
difference.
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; }}Complexity
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.
Trade-offs
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.
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.
Algorithm
- Create an integer array
t_indicesof size 26. - Iterate through string
tand populatet_indiceswheret_indices[char - 'a']stores the index ofcharint. - Initialize
totalDifference = 0. - Iterate through string
swith indexi. - For each character
c = s.charAt(i), get its index intfromt_indices[c - 'a']. - Add
|i - t_indices[c - 'a']|tototalDifference. - Return
totalDifference.
Walkthrough
The optimized algorithm proceeds in two main steps:
-
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 stringt. - Iterate through the string
tfromi = 0tot.length() - 1. - For each character
c = t.charAt(i), store its indexiin the array at the position corresponding to that character:t_indices[c - 'a'] = i.
- Create an integer array, let's call it
-
Calculation:
- Initialize a variable
differenceto 0. - Iterate through the string
swith an indexifrom 0 tos.length() - 1. - For each character
c = s.charAt(i), its index insisi. - Retrieve its index in
tdirectly from our precomputed array:j = t_indices[c - 'a']. - Calculate the absolute difference
Math.abs(i - j)and add it to thedifferencevariable.
- Initialize a variable
-
After iterating through
s, return the totaldifference.
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; }}Complexity
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.
Trade-offs
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.
Solutions
Solution
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; }}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; }}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; }};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))Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.