Skip to content

3146. Permutation Difference between Two Strings 👍

  • Time: $O(n)$
  • Space: $O(26) = O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
 public:
  int findPermutationDifference(string s, string t) {
    int ans = 0;
    vector<int> indices(26);

    for (int i = 0; i < s.length(); ++i)
      indices[s[i] - 'a'] = i;

    for (int i = 0; i < t.length(); ++i)
      ans += abs(indices[t[i] - 'a'] - i);

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
  public int findPermutationDifference(String s, String t) {
    int ans = 0;
    int[] indices = new int[26];

    for (int i = 0; i < s.length(); ++i)
      indices[s.charAt(i) - 'a'] = i;

    for (int i = 0; i < t.length(); ++i)
      ans += Math.abs(indices[t.charAt(i) - 'a'] - i);

    return ans;
  }
}

1
2
3
4
class Solution:
  def findPermutationDifference(self, s: str, t: str) -> int:
    indices = {c: i for i, c in enumerate(s)}
    return sum([abs(indices[c] - i) for i, c in enumerate(t)])