LeetCode 3146 - Permutation Difference between Two Strings

LeetCode Problem 3146

Difficulty: 🟢 Easy
Topics: Hash Table, String

Solution

Problem Understanding

The problem asks us to compute the permutation difference between two strings, s and t. Both strings contain unique characters, and t is a permutation of s. The permutation difference is calculated by taking each character in s, finding its index in both s and t, and summing the absolute differences of these indices.

In simpler terms, we want to measure how "out of order" t is relative to s. If a character moves far from its original position in s to its new position in t, it contributes more to the total difference.

The input consists of two strings of length at most 26 (since all characters are unique lowercase English letters). This means the problem size is small, so even simple algorithms are feasible. Edge cases include the smallest string length (1 character), strings where the permutation difference is 0 (strings are identical), and strings where the permutation difference is maximized (characters reversed).

Approaches

Brute Force Approach

The simplest way is to iterate over each character in s, find its index in t using a linear search, calculate the absolute difference, and sum these values. This works correctly but has a time complexity of O(n^2) because for each of the n characters in s, we potentially scan all n characters in t.

Optimal Approach

The key observation is that we do not need to scan t repeatedly. We can preprocess t by creating a hash map that maps each character to its index. Then for each character in s, we can immediately retrieve its index in t in O(1) time. This reduces the total time complexity to O(n).

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^2)	O(1)	Linear search for each character in t
Optimal	O(n)	O(n)	Use hash map to store indices of t

Algorithm Walkthrough

1. Initialize a hash map t_index_map to store the index of each character in t.
2. Iterate over t and fill t_index_map such that t_index_map[char] = index.
3. Initialize a variable perm_diff to 0, which will accumulate the permutation difference.
4. Iterate over each character char and its index i in s.
5. Retrieve the index of char in t from t_index_map.
6. Calculate the absolute difference abs(i - t_index_map[char]) and add it to perm_diff.
7. After the loop, return perm_diff.

Why it works: By precomputing the index of each character in t, we guarantee that for each character in s, we can directly calculate its positional difference without repeated scanning. This ensures the sum is correct and computed efficiently.

Python Solution

class Solution:
    def findPermutationDifference(self, s: str, t: str) -> int:
        t_index_map = {char: i for i, char in enumerate(t)}
        perm_diff = 0
        for i, char in enumerate(s):
            perm_diff += abs(i - t_index_map[char])
        return perm_diff

The Python solution uses a dictionary comprehension to map characters to their indices in t, which allows for O(1) lookups. Then it iterates through s, calculates the absolute difference for each character, and accumulates the total.

Go Solution

func findPermutationDifference(s string, t string) int {
    tIndexMap := make(map[rune]int)
    for i, ch := range t {
        tIndexMap[ch] = i
    }
    permDiff := 0
    for i, ch := range s {
        permDiff += abs(i - tIndexMap[ch])
    }
    return permDiff
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

The Go version uses a map[rune]int for the index map. A helper function abs computes the absolute difference because Go does not have a built-in abs for integers. Otherwise, the logic mirrors the Python solution.

Worked Examples

Example 1

s = "abc", t = "bac"

t_index_map = {"b":0, "a":1, "c":2}

char	index in s	index in t	abs diff	cumulative sum
a	0	1	1	1
b	1	0	1	2
c	2	2	0	2

Output: 2

Example 2

s = "abcde", t = "edbac"

t_index_map = {"e":0, "d":1, "b":2, "a":3, "c":4}

char	index in s	index in t	abs diff	cumulative sum
a	0	3	3	3
b	1	2	1	4
c	2	4	2	6
d	3	1	2	8
e	4	0	4	12

Output: 12

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Building the index map takes O(n), and computing the sum also takes O(n).
Space	O(n)	The hash map storing indices of t has size n.

The algorithm is linear because every operation depends on a single pass through the strings, and the hash map allows constant-time lookups.

Test Cases

# Basic examples
assert Solution().findPermutationDifference("abc", "bac") == 2  # example 1
assert Solution().findPermutationDifference("abcde", "edbac") == 12  # example 2

# Single character
assert Solution().findPermutationDifference("a", "a") == 0

# Identical strings
assert Solution().findPermutationDifference("xyz", "xyz") == 0

# Reverse order
assert Solution().findPermutationDifference("abcd", "dcba") == 6

# Two characters swapped
assert Solution().findPermutationDifference("ab", "ba") == 2

Test	Why
"abc" vs "bac"	Validates basic permutation difference
"abcde" vs "edbac"	Tests multiple swaps and sum correctness
"a" vs "a"	Edge case with minimal input size
"xyz" vs "xyz"	Edge case where permutation difference is 0
"abcd" vs "dcba"	Checks maximum difference for small n
"ab" vs "ba"	Simple swap edge case

Edge Cases

1. Single-character strings: The difference is always 0 because there is only one position. The algorithm handles this naturally because the loop runs once and abs(0-0) is 0.
2. Identical strings: If s and t are the same, the difference is 0. The algorithm calculates abs(i - i) for every character, ensuring the result is 0.
3. Reverse order strings: If t is the reverse of s, the algorithm still works because the absolute difference calculation does not assume any specific order. The sum of differences reflects the total "distance" each character moved. This can stress test correct index mapping.

This solution is robust, efficient, and handles all constraints specified by the problem.