Permutation Difference between Two Strings

Easy
540.

Permutation Difference between Two Strings

Permutation Difference between Two Strings is an easy coding problem on strings and hash table, asked in Amazon and Google interviews.

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 <= 26
  • Every character in s occurs at most once.
  • t is a permutation of s.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @param {string} t
 * @return {number}
 */
var findPermutationDifference = function(s, t) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 <= 26
  • Every character in s occurs at most once.
  • t is a permutation of s.

Hints for Permutation Difference between Two Strings

  1. Hint 1

    Record each character's index in t first.

  2. Hint 2

    Then walk s and accumulate |i - pos[s[i]]|.

  3. 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

  1. Build pos, mapping each character of t to its index.
  2. Sweep s, adding |i - pos[s[i]]| to a running total.
  3. 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 t for each character with indexOf inside 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