Mutating counts without cleanup
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.
Build confidence with an intuition-first walkthrough focused on hash map fundamentals.
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:
"a" in s and the index of the occurrence of "a" in t."b" in s and the index of the occurrence of "b" in t."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:
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 <= 26s.t is a permutation of s.s consists only of lowercase English letters.Problem summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Hash Map
"abc" "bac"
"abcde" "edbac"
find-the-difference)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #3146: Permutation Difference between Two Strings
class Solution {
public int findPermutationDifference(String s, String t) {
int[] d = new int[26];
int n = s.length();
for (int i = 0; i < n; ++i) {
d[s.charAt(i) - 'a'] = i;
}
int ans = 0;
for (int i = 0; i < n; ++i) {
ans += Math.abs(d[t.charAt(i) - 'a'] - i);
}
return ans;
}
}
// Accepted solution for LeetCode #3146: Permutation Difference between Two Strings
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
}
# Accepted solution for LeetCode #3146: Permutation Difference between Two Strings
class Solution:
def findPermutationDifference(self, s: str, t: str) -> int:
d = {c: i for i, c in enumerate(s)}
return sum(abs(d[c] - i) for i, c in enumerate(t))
// Accepted solution for LeetCode #3146: Permutation Difference between Two Strings
/**
* [3146] Permutation Difference between Two Strings
*/
pub struct Solution {}
// submission codes start here
use std::collections::HashMap;
impl Solution {
pub fn find_permutation_difference(s: String, t: String) -> i32 {
let mut map = HashMap::new();
for (i, c) in s.chars().enumerate() {
map.insert(c, i as i32);
}
let mut result = 0;
for (i, c) in t.chars().enumerate() {
let target = map.get(&c).unwrap();
result += (i as i32 - *target).abs()
}
result
}
}
// submission codes end
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_3146() {
assert_eq!(
2,
Solution::find_permutation_difference("abc".to_owned(), "bac".to_owned())
);
}
}
// Accepted solution for LeetCode #3146: Permutation Difference between Two Strings
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;
}
Use this to step through a reusable interview workflow for this problem.
For each element, scan the rest of the array looking for a match. Two nested loops give n × (n−1)/2 comparisons = O(n²). No extra space since we only use loop indices.
One pass through the input, performing O(1) hash map lookups and insertions at each step. The hash map may store up to n entries in the worst case. This is the classic space-for-time tradeoff: O(n) extra memory eliminates an inner loop.
Review these before coding to avoid predictable interview regressions.
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.