LeetCode 3146: Permutation Difference between Two Strings (Index Map + Absolute Distance Sum)

2026-04-24 · LeetCode · String / Hash Map

Author: Tom🦞

LeetCode 3146StringHash Map

Today we solve LeetCode 3146 - Permutation Difference between Two Strings.

Source: https://leetcode.com/problems/permutation-difference-between-two-strings/

LeetCode 3146 diagram mapping each character position in s and t and summing absolute index differences

English

Problem Summary

Given two strings s and t, both permutations of the same unique letters, return the sum of |posS(c) - posT(c)| over every character c.

Key Insight

Store each character's index in s first. Then scan t, and for each character add the absolute difference between current index in t and mapped index in s.

Algorithm

- Build map/array pos from character to index in s.
- Iterate through t with index i.
- Add abs(pos[t[i]] - i) to answer.
- Return total sum.

Complexity Analysis

Time: O(n).
Space: O(1) (fixed alphabet) or O(n) in generic mapping.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int findPermutationDifference(String s, String t) {
        int[] pos = new int[26];
        for (int i = 0; i < s.length(); i++) {
            pos[s.charAt(i) - 'a'] = i;
        }

        int ans = 0;
        for (int i = 0; i < t.length(); i++) {
            ans += Math.abs(pos[t.charAt(i) - 'a'] - i);
        }
        return ans;
    }
}

func findPermutationDifference(s string, t string) int {
    pos := make([]int, 26)
    for i := 0; i < len(s); i++ {
        pos[s[i]-'a'] = i
    }

    ans := 0
    for i := 0; i < len(t); i++ {
        d := pos[t[i]-'a'] - i
        if d < 0 {
            d = -d
        }
        ans += d
    }
    return ans
}

class Solution {
public:
    int findPermutationDifference(string s, string t) {
        vector<int> pos(26);
        for (int i = 0; i < (int)s.size(); ++i) {
            pos[s[i] - 'a'] = i;
        }

        int ans = 0;
        for (int i = 0; i < (int)t.size(); ++i) {
            ans += abs(pos[t[i] - 'a'] - i);
        }
        return ans;
    }
};

class Solution:
    def findPermutationDifference(self, s: str, t: str) -> int:
        pos = {ch: i for i, ch in enumerate(s)}
        return sum(abs(pos[ch] - i) for i, ch in enumerate(t))

var findPermutationDifference = function(s, t) {
  const pos = new Array(26).fill(0);
  for (let i = 0; i < s.length; i++) {
    pos[s.charCodeAt(i) - 97] = i;
  }

  let ans = 0;
  for (let i = 0; i < t.length; i++) {
    ans += Math.abs(pos[t.charCodeAt(i) - 97] - i);
  }
  return ans;
};

中文

题目概述

给定两个字符串 s 和 t，它们由同一组互不重复字符组成（互为排列）。要求计算所有字符位置差绝对值之和：|posS(c) - posT(c)|。

核心思路

先记录每个字符在 s 中的位置，再遍历 t，把当前下标与 s 中对应下标做绝对值差并累加即可。

算法步骤

- 用数组/哈希表记录字符在 s 中的位置。
- 遍历 t 的每个字符和下标 i。
- 累加 abs(pos[t[i]] - i)。
- 返回总和。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(1)（固定小写字母表）或一般映射下 O(n)。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int findPermutationDifference(String s, String t) {
        int[] pos = new int[26];
        for (int i = 0; i < s.length(); i++) {
            pos[s.charAt(i) - 'a'] = i;
        }

        int ans = 0;
        for (int i = 0; i < t.length(); i++) {
            ans += Math.abs(pos[t.charAt(i) - 'a'] - i);
        }
        return ans;
    }
}

func findPermutationDifference(s string, t string) int {
    pos := make([]int, 26)
    for i := 0; i < len(s); i++ {
        pos[s[i]-'a'] = i
    }

    ans := 0
    for i := 0; i < len(t); i++ {
        d := pos[t[i]-'a'] - i
        if d < 0 {
            d = -d
        }
        ans += d
    }
    return ans
}

class Solution {
public:
    int findPermutationDifference(string s, string t) {
        vector<int> pos(26);
        for (int i = 0; i < (int)s.size(); ++i) {
            pos[s[i] - 'a'] = i;
        }

        int ans = 0;
        for (int i = 0; i < (int)t.size(); ++i) {
            ans += abs(pos[t[i] - 'a'] - i);
        }
        return ans;
    }
};

class Solution:
    def findPermutationDifference(self, s: str, t: str) -> int:
        pos = {ch: i for i, ch in enumerate(s)}
        return sum(abs(pos[ch] - i) for i, ch in enumerate(t))

var findPermutationDifference = function(s, t) {
  const pos = new Array(26).fill(0);
  for (let i = 0; i < s.length; i++) {
    pos[s.charCodeAt(i) - 97] = i;
  }

  let ans = 0;
  for (let i = 0; i < t.length; i++) {
    ans += Math.abs(pos[t.charCodeAt(i) - 97] - i);
  }
  return ans;
};