DEV Community

Cover image for Leetcode — 3146. Permutation Difference between Two Strings
Ben Pereira
Ben Pereira

Posted on

Leetcode — 3146. Permutation Difference between Two Strings

It’s an easy problem with description being:

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.

There is a lot of pretty words to describe what needs to be done, but once you see one example it makes it easier to understand what is that the problem is trying to accomplish.

Following the permutation difference calculation there is an understatement that needs to be done is:

  • Iterate the String;
  • Retrieve the character based on the index;
  • Find this character index on the second String;
  • Subtract first index with second one;
  • Get the absolute value from that subtraction and collect all into one output.

Now let’s translate that thought into java code:

class Solution {
    public int findPermutationDifference(String s, String t) {

        int output = 0;

        for(int i=0; i <s.length(); i++) {
            final char c = s.charAt(i);
            final int j = t.indexOf(c);
            output += Math.abs(i - j);
        }

        return output;
    }
}
Enter fullscreen mode Exit fullscreen mode

Runtime: 1ms, faster than 100% of Java online submissions.

Memory Usage: 42.67 MB, less than 57.64% of Java online submissions.

That’s a good solution that’s also very good performance wise. If we want to be more elegant and follow the solution with a Stream the solution would be:

class Solution {
    public int findPermutationDifference(String s, String t) {
        return IntStream.range(0, s.length())
                   .map(i -> findCharPermutationDifference(s,t,i))
                   .sum();
    }

    public int findCharPermutationDifference(final String s, final String t, final int i) {
        final char c = s.charAt(i);
        final int j = t.indexOf(c);
        return Math.abs(i - j);
    }
}
Enter fullscreen mode Exit fullscreen mode

Runtime: 5ms, faster than 2.31% of Java online submissions.

Memory Usage: 43.02 MB, less than 23.05% of Java online submissions.

Not as good performance and memory wise, but ellegant nonetheless.

That’s it! If there is anything thing else to discuss feel free to drop a comment, if I missed anything let me know so I can update accordingly.

Until next post! :)

Top comments (0)