Scale Engineer

Permutation Difference between Two Strings

Easy
#2795Time: O(n^2), where n is the length of the strings. The nested loops result in a quadratic time complexity, as for each of the n characters in `s`, we might have to scan all n characters of `t` in the worst case.Space: O(1). No extra space proportional to the input size is used. We only use a few variables for the sum and loop counters.1 company
Data structures
Hash TableString
Companies
Accenture

Prompt

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" in s and the index of the occurrence of "a" in t.
  • The absolute difference between the index of the occurrence of "b" in s and the index of the occurrence of "b" in t.
  • The absolute difference between the index of the occurrence of "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 <= 26
  • Each character occurs at most once in s.
  • t is a permutation of s.
  • s consists only of lowercase English letters.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly translates the problem definition into code. We iterate through each character of the first string s. For each character, we then perform a search in the second string t to find the same character and its index. The absolute difference of the indices is then added to a running total.

Algorithm

  • Initialize a variable difference to 0.
  • Iterate through the string s with an index i from 0 to s.length() - 1.
  • For each character s.charAt(i), start a nested loop to iterate through the string t with an index j from 0 to t.length() - 1.
  • Inside the inner loop, if s.charAt(i) matches t.charAt(j), calculate the absolute difference of their indices, |i - j|.
  • Add this difference to the difference variable.
  • Break the inner loop since characters are unique.
  • After the outer loop completes, return the total difference.

Walkthrough

The algorithm works as follows:

  1. Initialize a variable difference to 0. This will store the sum of the absolute index differences.
  2. Iterate through the string s with an index i from 0 to s.length() - 1.
  3. For each character s.charAt(i), start a nested loop to iterate through the string t with an index j from 0 to t.length() - 1.
  4. Inside the inner loop, check if the character from s matches the character from t (i.e., s.charAt(i) == t.charAt(j)).
  5. If they match, calculate the absolute difference of their indices: Math.abs(i - j).
  6. Add this difference to the difference variable.
  7. Since each character is unique, we can break the inner loop once a match is found and proceed to the next character in s.
  8. After the outer loop completes, return the total difference.
class Solution {    public int findPermutationDifference(String s, String t) {        int n = s.length();        int totalDifference = 0;        for (int i = 0; i < n; i++) {            char charS = s.charAt(i);            for (int j = 0; j < n; j++) {                if (charS == t.charAt(j)) {                    totalDifference += Math.abs(i - j);                    break; // Character found, break inner loop                }            }        }        return totalDifference;    }}

Complexity

Time

O(n^2), where n is the length of the strings. The nested loops result in a quadratic time complexity, as for each of the n characters in `s`, we might have to scan all n characters of `t` in the worst case.

Space

O(1). No extra space proportional to the input size is used. We only use a few variables for the sum and loop counters.

Trade-offs

Pros

  • Very simple to conceptualize and implement.

  • Does not require any auxiliary data structures.

Cons

  • Inefficient for longer strings due to the quadratic time complexity.

  • The performance degrades quickly as the string length increases.

Solutions

public 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[i] - 'a'] = i;        }        int ans = 0;        for (int i = 0; i < n; ++i) {            ans += Math.Abs(d[t[i] - 'a'] - i);        }        return ans;    }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem