We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Permutation Difference between Two Strings

Difficulty: Easy

Problem Description

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.

Key Insights

  • Each character in the strings occurs only once, allowing for direct index comparisons.
  • The permutation difference can be computed by summing the absolute differences of indices for each character.
  • A hash table (or dictionary) can efficiently map each character to its index for quick lookups.

Space and Time Complexity

Time Complexity: O(n) - where n is the length of the strings, since we traverse both strings once. Space Complexity: O(n) - for storing the indices of characters in a hash table.

Solution

To solve the problem, we can follow these steps:

  1. Create a hash table to store the indices of each character in string s.
  2. Iterate through each character in string t, retrieving its index from the hash table.
  3. Calculate the absolute difference between the indices from s and t for each character and keep a running total.

This approach efficiently computes the permutation difference by leveraging the properties of hash tables for quick index retrieval.

Code Solutions

def permutation_difference(s: str, t: str) -> int:
    index_map = {char: idx for idx, char in enumerate(s)}  # Create a map of characters to their indices
    total_difference = 0  # Initialize total difference

    for idx, char in enumerate(t):  # Iterate through each character in t
        total_difference += abs(idx - index_map[char])  # Calculate and accumulate the absolute difference

    return total_difference  # Return the total permutation difference
← Back to All Questions