Permutation Difference between Two Strings — Solution
Permutation Difference between Two Strings solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Permutation Difference between Two Strings is an easy coding problem on strings and hash table, asked in Amazon and Google interviews.
- Difficulty: Easy
- Topics: Strings, Hash Table
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given two strings s and t where t is a permutation of s, and every character in s is distinct.
The permutation difference is the sum, over all characters, of the absolute difference between the character's index in s and its index in t.
Return that value.
Example 1
Input: s = "abc", t = "bac"
Output: 2
Explanation: a moves from 0 to 1 and b from 1 to 0; c does not move.
Example 2
Input: s = "abcde", t = "edbac"
Output: 12
Example 3
Input: s = "a", t = "a"
Output: 0
Constraints
1 <= s.length <= 26Every character in s occurs at most once.t is a permutation of s.
Hints for Permutation Difference between Two Strings
Hint 1
Record each character's index in
tfirst.Hint 2
Then walk
sand accumulate|i - pos[s[i]]|.Hint 3
Because characters are distinct, a plain map from character to index is unambiguous.
How to solve Permutation Difference between Two Strings
With distinct characters, each one has a single index in each string, so a lookup table over t turns the sum into one pass over s.
Approach
- Build
pos, mapping each character oftto its index. - Sweep
s, adding|i - pos[s[i]]|to a running total. - Return the total.
Why it works
Distinctness is what makes pos well defined; without it a character would have several indices and the pairing would be ambiguous.
Complexity
- Time —
O(n) - Space —
O(1) — at most 26 entries
Pitfalls
- Searching
tfor each character withindexOfinside the loop makes it O(n²) — harmless at n ≤ 26 but a bad habit. - Forgetting the absolute value lets forward and backward moves cancel.
Reference solution
Python
def findPermutationDifference(s: str, t: str) -> int:
pos = {c: i for i, c in enumerate(t)}
return sum(abs(i - pos[c]) for i, c in enumerate(s))Java
public static int findPermutationDifference(String s, String t) {
int[] pos = new int[26];
for (int i = 0; i < t.length(); i++) pos[t.charAt(i) - 'a'] = i;
int total = 0;
for (int i = 0; i < s.length(); i++) total += Math.abs(i - pos[s.charAt(i) - 'a']);
return total;
}C++
int findPermutationDifference(string s, string t) {
int pos[26] = { 0 };
for (int i = 0; i < (int) t.size(); i++) pos[t[i] - 'a'] = i;
int total = 0;
for (int i = 0; i < (int) s.size(); i++) total += abs(i - pos[s[i] - 'a']);
return total;
}JavaScript
var findPermutationDifference = function(s, t) {
const pos = {};
for (let i = 0; i < t.length; i++) pos[t.charAt(i)] = i;
let total = 0;
for (let i = 0; i < s.length; i++) total += Math.abs(i - pos[s.charAt(i)]);
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Hashing: Hash Maps and Hash Sets