Problem

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.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

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

1
2
3
4

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.

Solution

Method 1 - Index Mapping (Sum of Absolute Differences)

Intuition

Since each character occurs at most once in s and t is a permutation, we can build mappings idx_s and idx_t from character to index for s and t respectively, then sum the absolute differences of indices for each character.

Approach

Build a mapping idx_s from characters in s to their indices and a mapping idx_t for t. Initialize res = 0. For each character c in s, add abs(idx_s[c] - idx_t[c]) to res. Return res.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

#include <string>
#include <unordered_map>
#include <cmath>
using namespace std;
class Solution {
public:
    int permutationDifference(string s, string t) {
        unordered_map<char, int> idx_s, idx_t;
        for (int i = 0; i < s.size(); ++i) idx_s[s[i]] = i;
        for (int i = 0; i < t.size(); ++i) idx_t[t[i]] = i;
        int res = 0;
        for (auto& [c, i] : idx_s) res += abs(i - idx_t[c]);
        return res;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

func permutationDifference(s, t string) int {
    idxS := make(map[byte]int)
    idxT := make(map[byte]int)
    for i := 0; i < len(s); i++ { idxS[s[i]] = i }
    for i := 0; i < len(t); i++ { idxT[t[i]] = i }
    res := 0
    for c, i := range idxS { res += abs(i - idxT[c]) }
    return res
}
func abs(x int) int { if x < 0 { return -x }; return x }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

import java.util.*;
class Solution {
    public int permutationDifference(String s, String t) {
        Map<Character, Integer> idxS = new HashMap<>(), idxT = new HashMap<>();
        for (int i = 0; i < s.length(); i++) idxS.put(s.charAt(i), i);
        for (int i = 0; i < t.length(); i++) idxT.put(t.charAt(i), i);
        int res = 0;
        for (char c : idxS.keySet()) res += Math.abs(idxS.get(c) - idxT.get(c));
        return res;
    }
}
1
2
3
4
5
6
7

class Solution {
    fun permutationDifference(s: String, t: String): Int {
        val idxS = s.withIndex().associate { it.value to it.index }
        val idxT = t.withIndex().associate { it.value to it.index }
        return s.sumOf { kotlin.math.abs(idxS[it]!! - idxT[it]!!) }
    }
}
1
2
3
4

def permutationDifference(s: str, t: str) -> int:
    idx_s = {c: i for i, c in enumerate(s)}
    idx_t = {c: i for i, c in enumerate(t)}
    return sum(abs(idx_s[c] - idx_t[c]) for c in s)
1
2
3
4
5
6

use std::collections::HashMap;
fn permutation_difference(s: &str, t: &str) -> i32 {
    let idx_s: HashMap<_, _> = s.chars().enumerate().map(|(i, c)| (c, i as i32)).collect();
    let idx_t: HashMap<_, _> = t.chars().enumerate().map(|(i, c)| (c, i as i32)).collect();
    s.chars().map(|c| (idx_s[&c] - idx_t[&c]).abs()).sum()
}
1
2
3
4
5
6
7
8
9

function permutationDifference(s: string, t: string): number {
    const idxS: Record<string, number> = {};
    const idxT: Record<string, number> = {};
    for (let i = 0; i < s.length; i++) idxS[s[i]] = i;
    for (let i = 0; i < t.length; i++) idxT[t[i]] = i;
    let res = 0;
    for (const c of s) res += Math.abs(idxS[c] - idxT[c]);
    return res;
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n)