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! :)

AWS Security LIVE!

Join us for AWS Security LIVE!

Discover the future of cloud security. Tune in live for trends, tips, and solutions from AWS and AWS Partners.

Learn More

Top comments (0)

A Workflow Copilot. Tailored to You.

Pieces.app image

Our desktop app, with its intelligent copilot, streamlines coding by generating snippets, extracting code from screenshots, and accelerating problem-solving.

Read the docs

👋 Kindness is contagious

Dive into an ocean of knowledge with this thought-provoking post, revered deeply within the supportive DEV Community. Developers of all levels are welcome to join and enhance our collective intelligence.

Saying a simple "thank you" can brighten someone's day. Share your gratitude in the comments below!

On DEV, sharing ideas eases our path and fortifies our community connections. Found this helpful? Sending a quick thanks to the author can be profoundly valued.

Okay