Permutation Difference between Two Strings solution and explanation
8 more videos on this problem
3146. Permutation Difference between Two Strings | Permutation | EASY | LeetCode | String | MapLeet's Code · 2:56 · 1K views
3146. Permutation Difference between Two Strings (Leetcode Easy)Programming Live with Larry · 1:52 · 760 views
Leetcode 3146 Permutation Difference between Two StringsLuc Taylor · 1:56 · 242 views
100296. Permutation Difference between Two Strings || LeetCode ContestNaresh · 1:21 · 135 views
Leetcode easy problem 3146. Permutation Difference between Two Strings | devops python practiceADevOpsEngineer · 2:14 · 55 views
3146 Solved! Permutation Difference Between Two Strings LeetCode(Java/Python/C++) #StackSmack #fypシStackSmack · 6:38 · 47 views
leetcode 3146. Permutation Difference between Two Stringscomicfans44 · 0:57 · 42 views
weekly-contest-397 #contest #leetcode #Permutation## Difference between Two StringsJay prakash Kumar · 0:17 · 33 views
🔥 LeetCode 3146 – Permutation Difference Between Two Strings | C++ SolutionKamlesh Chandela · 7:28 · 9 views
The 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.
Example 1:
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"insand the index of the occurrence of"a"int. - The absolute difference between the index of the occurrence of
"b"insand the index of the occurrence of"b"int. - The absolute difference between the index of the occurrence of
"c"insand the index of the occurrence of"c"int.
That is, the permutation difference between s and t is equal to |0 - 1| + |1 - 0| + |2 - 2| = 2.
Example 2:
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. tis a permutation ofs.sconsists only of lowercase English letters.
Approach overview
Problem Overview: You get two strings s and t that are permutations of the same characters. For every character, compute the absolute difference between its index in s and its index in t, then sum all those differences. The task is essentially comparing the position of each character across two permutations.
Approach 1: Using Index Lookup (O(n) time, O(1) space)
Store the index of every character from s using a fixed array or direct index lookup. Since characters are lowercase English letters, you can use a size‑26 array where pos[c - 'a'] stores the position of that character in s. Iterate through t, look up the stored index from s, and add abs(i - pos[c]) to the running total. Each lookup and update is constant time, so the entire pass runs in linear time.
This approach is efficient because it replaces repeated searches with direct indexing. Instead of scanning the string for every character, the algorithm performs constant-time lookups. The space cost stays constant since the alphabet size is fixed. This method is common when solving Hash Table and String problems involving character positions.
Approach 2: Mapping with a Dictionary (O(n) time, O(n) space)
Create a dictionary (hash map) that maps each character in s to its index. Traverse s once and store map[char] = index. Then iterate through t, retrieve the stored index for each character, and accumulate the absolute difference between indices.
The dictionary provides average O(1) lookup time, keeping the overall complexity linear. This version is more flexible than the array lookup approach because it works even if the character set changes or includes non‑alphabet characters. The tradeoff is additional memory proportional to the number of distinct characters.
Both approaches rely on the same insight: the permutation difference only depends on where each character appears in the two strings. Instead of comparing entire strings repeatedly, store positions once and reuse them through constant‑time lookups.
Recommended for interviews: The index lookup approach is usually preferred. It demonstrates awareness of character constraints and reduces memory to O(1). Interviewers still accept the dictionary solution since it clearly applies the hash table pattern and keeps the algorithm clean and readable. Showing the dictionary version first and then optimizing to a fixed array highlights strong problem‑solving instincts.
Approach 1: Using Index Lookup
This approach leverages the ability to find the index of each character in a string efficiently. For each character in the string s, we find its index in both s and t and accumulate the absolute difference of these indices to compute the permutation difference.
def permutation_difference(s, t):
return sum(abs(s.index(char) - t.index(char)) for char in s)
# Example Usage
print(permutation_difference('abc', 'bac')) # Output: 2
print(permutation_difference('abcde', 'edbac')) # Output: 12public class PermutationDifference {
public static int permutationDifference(String s, String t) {
int diff = 0;
for (char c : s.toCharArray()) {
diff += Math.abs(s.indexOf(c) - t.indexOf(c));
}
return diff;
}
// Example Usage
public static void main(String[] args) {
System.out.println(permutationDifference("abc", "bac")); // Output: 2
System.out.println(permutationDifference("abcde", "edbac")); // Output: 12
}
}#include<iostream>
#include<cmath>
using namespace std;
int permutationDifference(string s, string t) {
int diff = 0;
for (char c : s) {
diff += abs((int)s.find(c) - (int)t.find(c));
}
return diff;
}
// Example Usage
int main() {
cout << permutationDifference("abc", "bac") << endl; // Output: 2
cout << permutationDifference("abcde", "edbac") << endl; // Output: 12
return 0;
}function permutationDifference(s, t) {
let diff = 0;
for (const char of s) {
diff += Math.abs(s.indexOf(char) - t.indexOf(char));
}
return diff;
}
// Example Usage
console.log(permutationDifference('abc', 'bac')); // Output: 2
console.log(permutationDifference('abcde', 'edbac')); // Output: 12#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int permutationDifference(char *s, char *t) {
int diff = 0;
for (int i = 0; i < strlen(s); i++) {
int s_index = strchr(s, s[i]) - s;
int t_index = strchr(t, s[i]) - t;
diff += abs(s_index - t_index);
}
return diff;
}
// Example Usage
int main() {
printf("%d\n", permutationDifference("abc", "bac")); // Output: 2
printf("%d\n", permutationDifference("abcde", "edbac")); // Output: 12
return 0;
}using System;
public class PermutationDifference {
public static int GetPermutationDifference(string s, string t) {
int diff = 0;
foreach (char c in s) {
diff += Math.Abs(s.IndexOf(c) - t.IndexOf(c));
}
return diff;
}
// Example Usage
public static void Main() {
Console.WriteLine(GetPermutationDifference("abc", "bac")); // Output: 2
Console.WriteLine(GetPermutationDifference("abcde", "edbac")); // Output: 12
}
}We iterate over each character in string s. For each character, we calculate the index in string s and t. The absolute difference between these indices is added to the total sum, which is the permutation difference.
Time Complexity: O(n^2), where n is the length of the string. This is because for each character, we perform an index lookup which is O(n).
Space Complexity: O(1), as we are only using a few variables to store intermediate results.
Approach 2: Mapping with a Dictionary
This approach optimizes index retrieval by constructing a map for each character's index in both strings before calculating differences. The process is thus streamlined, with quick look-ups during the difference calculation phase.
def permutation_difference(s, t):
s_index_map = {char: idx for idx, char in enumerate(s)}
t_index_map = {char: idx for idx, char in enumerate(t)}
return sum(abs(s_index_map[char] - t_index_map[char]) for char in s)
# Example Usage
print(permutation_difference('abc', 'bac')) # Output: 2
print(permutation_difference('abcde', 'edbac')) # Output: 12import java.util.HashMap;
public class PermutationDifference {
public static int permutationDifference(String s, String t) {
HashMap<Character, Integer> sIndexMap = new HashMap<>();
HashMap<Character, Integer> tIndexMap = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
sIndexMap.put(s.charAt(i), i);
tIndexMap.put(t.charAt(i), i);
}
int diff = 0;
for (char c : s.toCharArray()) {
diff += Math.abs(sIndexMap.get(c) - tIndexMap.get(c));
}
return diff;
}
// Example Usage
public static void main(String[] args) {
System.out.println(permutationDifference("abc", "bac")); // Output: 2
System.out.println(permutationDifference("abcde", "edbac")); // Output: 12
}
}#include <iostream>
#include <unordered_map>
#include <cmath>
using namespace std;
int permutationDifference(string s, string t) {
unordered_map<char, int> sIndexMap;
unordered_map<char, int> tIndexMap;
for (int i = 0; i < s.length(); i++) {
sIndexMap[s[i]] = i;
tIndexMap[t[i]] = i;
}
int diff = 0;
for (char c : s) {
diff += abs(sIndexMap[c] - tIndexMap[c]);
}
return diff;
}
// Example Usage
int main() {
cout << permutationDifference("abc", "bac") << endl; // Output: 2
cout << permutationDifference("abcde", "edbac") << endl; // Output: 12
return 0;
}function permutationDifference(s, t) {
const sIndexMap = {};
const tIndexMap = {};
for (let i = 0; i < s.length; i++) {
sIndexMap[s[i]] = i;
tIndexMap[t[i]] = i;
}
let diff = 0;
for (const char of s) {
diff += Math.abs(sIndexMap[char] - tIndexMap[char]);
}
return diff;
}
// Example Usage
console.log(permutationDifference('abc', 'bac')); // Output: 2
console.log(permutationDifference('abcde', 'edbac')); // Output: 12#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int permutationDifference(char *s, char *t) {
int indexes_s[256] = {0};
int indexes_t[256] = {0};
for (int i = 0; i < strlen(s); i++) {
indexes_s[s[i]] = i;
indexes_t[t[i]] = i;
}
int diff = 0;
for (int i = 0; i < strlen(s); i++) {
diff += abs(indexes_s[s[i]] - indexes_t[s[i]]);
}
return diff;
}
// Example Usage
int main() {
printf("%d\n", permutationDifference("abc", "bac")); // Output: 2
printf("%d\n", permutationDifference("abcde", "edbac")); // Output: 12
return 0;
}using System;
using System.Collections.Generic;
public class PermutationDifference {
public static int GetPermutationDifference(string s, string t) {
Dictionary<char, int> sIndexMap = new Dictionary<char, int>();
Dictionary<char, int> tIndexMap = new Dictionary<char, int>();
for (int i = 0; i < s.Length; i++) {
sIndexMap[s[i]] = i;
tIndexMap[t[i]] = i;
}
int diff = 0;
foreach (char c in s) {
diff += Math.Abs(sIndexMap[c] - tIndexMap[c]);
}
return diff;
}
// Example Usage
public static void Main() {
Console.WriteLine(GetPermutationDifference("abc", "bac")); // Output: 2
Console.WriteLine(GetPermutationDifference("abcde", "edbac")); // Output: 12
}
}We first create mapping dictionaries for the indices of characters in both s and t. These mappings allow O(1) retrieval of character positions, leading to efficient computation of the permutation difference.
Time Complexity: O(n), since each map is constructed in O(n) time and each index retrieval is O(1).
Space Complexity: O(n), because of the additional data structures for mapping.
Approach 3: Hash Table or Array
We can use a hash table or an array of length 26, denoted as d, to store the positions of each character in the string s.
Then, we traverse the string t and calculate the sum of the absolute differences between the positions of each character in the string t and the positions in the string s.
The time complexity is O(n), where n is the length of the string s. The space complexity is O(|\Sigma|), where \Sigma is the character set. Here, it is lowercase English letters, so |\Sigma| leq 26.
function findPermutationDifference(s: string, t: string): number {
const d: number[] = Array(26).fill(0);
const n = s.length;
for (let i = 0; i < n; ++i) {
d[s.charCodeAt(i) - 97] = i;
}
let ans = 0;
for (let i = 0; i < n; ++i) {
ans += Math.abs(d[t.charCodeAt(i) - 97] - i);
}
return ans;
}func findPermutationDifference(s string, t string) (ans int) {
d := [26]int{}
for i, c := range s {
d[c-'a'] = i
}
for i, c := range t {
ans += max(d[c-'a']-i, i-d[c-'a'])
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Using Index Lookup | Time Complexity: O(n^2), where n is the length of the string. This is because for each character, we perform an index lookup which is O(n). |
| Mapping with a Dictionary | Time Complexity: O(n), since each map is constructed in O(n) time and each index retrieval is O(1). |
| Hash Table or Array | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Index Lookup with Fixed Array | O(n) | O(1) | Best when characters are limited (e.g., lowercase letters). Fastest and most memory‑efficient. |
| Mapping with Dictionary | O(n) | O(n) | General solution when character set may vary or constraints are unknown. |
Frequently asked questions
Is Permutation Difference between Two Strings easy or hard?
Permutation Difference between Two Strings is classified as an Easy problem. The logic mainly involves storing character indices and performing simple arithmetic during a linear traversal.
Permutation Difference between Two Strings Python/Java solution
Python and Java implementations typically build a dictionary or map of character positions from the first string, then iterate through the second string computing absolute index differences. Both versions run in O(n) time and use either O(n) or O(1) space depending on the implementation.
How to solve Permutation Difference between Two Strings in O(n)?
First store the index of every character in s using either a hash map or a fixed array. Then iterate through t and compute abs(i - stored_index) for each character. Summing these values across the string produces the permutation difference in a single pass.
What is the best approach for Permutation Difference between Two Strings?
The most efficient approach stores the index of each character from string s and then scans string t while computing the absolute index difference. Using a fixed array for character positions achieves O(n) time and O(1) space when the alphabet size is limited.
Is Permutation Difference between Two Strings asked at Google/Amazon/Meta?
Permutation and string-index comparison problems appear frequently in interviews at companies like Amazon, Google, and Meta. Variations often test hash table usage, character indexing, and efficient string traversal patterns.
What data structure is used in Permutation Difference between Two Strings?
The common data structure is a hash table or dictionary that maps each character to its index. When the character set is fixed, a small array can replace the hash table for faster lookups and constant space usage.
What is the time complexity of Permutation Difference between Two Strings?
The optimal solution runs in O(n) time because each string is processed once. Index lookups from an array or hash map take constant time, so the total work grows linearly with the string length.