Permutation Difference between Two Strings

Permutation Difference between Two Strings - 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.

Input & Output

Example 1 — Basic Case

$ Input: s = "abc", t = "bac"

› Output: 2

💡 Note: Character 'a': position 0 in s, position 1 in t → |0-1| = 1. Character 'b': position 1 in s, position 0 in t → |1-0| = 1. Character 'c': position 2 in s, position 2 in t → |2-2| = 0. Total: 1+1+0 = 2

Example 2 — No Movement

$ Input: s = "ab", t = "ab"

› Output: 0

💡 Note: Both strings are identical, so no characters moved positions. All differences are 0.

Example 3 — Complete Reversal

$ Input: s = "abcde", t = "edcba"

› Output: 12

💡 Note: Each character moved to the opposite end: 'a' moved 4 positions, 'b' moved 2, 'c' stayed, 'd' moved 2, 'e' moved 4. Total: 4+2+0+2+4 = 12

Constraints

1 ≤ s.length ≤ 26
Each character occurs at most once in s
t is a permutation of s

Visualization

Tap to expand

Understanding the Visualization

Input Strings

Two strings s and t where t is a permutation of s

Find Differences

For each character, calculate |position_in_s - position_in_t|

Sum Total

Add all individual differences to get final result

Key Takeaway

🎯 Key Insight: Use a hash map to store positions from string t for instant O(1) character lookups

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is to use a hash map to store character positions from string t, enabling O(1) lookups. Best approach is the two-pass hash map solution. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Hash Map Optimization	O(n)	O(n)	Build position map for t, then calculate differences in one pass through s
Brute Force Search	O(n²)	O(1)	For each character in s, search through t to find its position

Hash Map Optimization — Algorithm Steps

Build hash map: character → position for string t
Iterate through s and lookup each character's position in t
Calculate |s_index - t_index| and sum all differences

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Map

Create character → position mapping for string t

Lookup & Calculate

For each char in s, instantly find its position in t

Sum Differences

Add all |i - j| values to get total

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(char* s, char* t) {
    // Build position array for ASCII characters
    int pos[256];
    memset(pos, -1, sizeof(pos));
    
    int len = strlen(t);
    for (int i = 0; i < len; i++) {
        pos[(unsigned char)t[i]] = i;
    }
    
    // Calculate total difference
    int totalDiff = 0;
    for (int i = 0; i < len; i++) {
        totalDiff += abs(i - pos[(unsigned char)s[i]]);
    }
    
    return totalDiff;
}

int main() {
    char s[1001], t[1001];
    fgets(s, sizeof(s), stdin);
    fgets(t, sizeof(t), stdin);
    s[strcspn(s, "\n")] = 0;
    t[strcspn(t, "\n")] = 0;
    int result = solution(s, t);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Two separate O(n) passes: one to build hash map, one to calculate differences

✓ Linear Growth

Space Complexity

O(n)

Hash map stores position for each of the n characters

⚡ Linearithmic Space

12.5K Views

Medium Frequency

~10 min Avg. Time

342 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Hash Map Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler