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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Permutation Difference between Two Strings

Number: 3412

Difficulty: Easy

Paid? No

Companies: Accenture

Problem Description

Given two strings s and t, where every character in s is unique and t is a permutation of s, calculate the permutation difference. The permutation difference is defined as the sum of the absolute differences between the indices of each character in s and its corresponding index in t.

Key Insights

  • Since s contains unique characters, we can easily map each character to its index.
  • Create a hash map (or dictionary) for one of the strings (e.g., s) for constant time lookups.
  • Iterate over the characters, find their positions in s and t, and sum the absolute differences of these positions.
  • The constraints guarantee small input size (max 26 characters), so simplicity in design is acceptable.

Space and Time Complexity

Time Complexity: O(n) where n is the length of string s (or t). Space Complexity: O(n) for storing the index mapping.

Solution

We map each character in s to its index using a hash table (or dictionary). Then, we iterate over each character in t, lookup its index from the mapping, and compute the absolute difference between this index and the current index in t. Summing these absolute differences gives us the required permutation difference.

Code Solutions

# Python solution with line-by-line comments
def permutation_difference(s: str, t: str) -> int:
    # Create a dictionary mapping each character in s to its index.
    s_indexes = {char: idx for idx, char in enumerate(s)}
    total_difference = 0
    # Iterate over each character in t along with its index.
    for idx, char in enumerate(t):
        # Look up the index of char in s using the dictionary.
        s_idx = s_indexes[char]
        # Add the absolute difference between the indices in s and t.
        total_difference += abs(s_idx - idx)
    return total_difference

# Example usage
if __name__ == "__main__":
    s = "abcde"
    t = "edbac"
    print(permutation_difference(s, t))  # Output: 12
← Back to All Questions