Leet Code — 2744. Find Maximum Number of String Pairs

It’s an easy problem with the description being:

You are given a 0-indexed array words consisting of distinct strings.

The string words[i] can be paired with the string words[j] if:

The string words[i] is equal to the reversed string of words[j].

0 <= i < j < words.length.

Return the maximum number of pairs that can be formed from the array words.

Note that each string can belong in at most one pair.

Example 1:
Input: words = ["cd","ac","dc","ca","zz"]

Output: 2
Explanation: In this example, we can form 2 pair of strings in the following way:

• We pair the 0th string with the 2nd string, as the reversed string of word[0] is "dc" and is equal to words[2].
• We pair the 1st string with the 3rd string, as the reversed string of word[1] is "ca" and is equal to words[3]. It can be proven that 2 is the maximum number of pairs that can be formed.

Example 2:
Input: words = ["ab","ba","cc"]

Output: 1
Explanation: In this example, we can form 1 pair of strings in the following way:

• We pair the 0th string with the 1st string, as the reversed string of words[1] is "ab" and is equal to words[0]. It can be proven that 1 is the maximum number of pairs that can be formed.

Example 3:
Input: words = ["aa","ab"]

Output: 0
Explanation: In this example, we are unable to form any pair of strings.

Constraints:

1 <= words.length <= 50
words[i].length == 2
words consists of distinct strings.
words[i] contains only lowercase English letters.

Here a way to get this done would be two iterations, the first one passing through each word, and from word you will reverse and compare with the rest of the words, for example:

class Solution {
    public int maximumNumberOfStringPairs(String[] words) {
        int maxPairs = 0;

        for(int i=0;i<words.length;i++){
            final String word = words[i];
            final String wordReversed = word.charAt(1) + "" +  word.charAt(0);

            for(int j=(i+1);j<words.length;j++){
                if(words[j].equals(wordReversed)) {
                    maxPairs++;
                }
            }
        }

        return maxPairs;
    }
}

Runtime: 8 ms, faster than 27.17% of Java online submissions for Find Maximum Number of String Pairs.

Memory Usage: 42.3 MB, less than 75.70% of Java online submissions for Find Maximum Number of String Pairs.

One way to give a better performance would be to instead of make instances and references of String making character comparisons straight away:

class Solution {
    public int maximumNumberOfStringPairs(String[] words) {
        int maxPairs = 0;

        for(int i=0;i<words.length;i++){
            for(int j=(i+1);j<words.length;j++){
                if(words[i].charAt(0) == words[j].charAt(1) && words[i].charAt(1) == words[j].charAt(0)) {
                    maxPairs++;
                }
            }
        }

        return maxPairs;
    }
}

Runtime: 1 ms, faster than 100.00% of Java online submissions for Find Maximum Number of String Pairs.

Memory Usage: 41.6 MB, less than 79.74% of Java online submissions for Find Maximum Number of String Pairs.

Simpler, faster, straight to the point and if you want to make it more readable you could replace the conditions with methods explaining more the process.

---

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

Comments

[Jonas Scholz]

This is O(n^2), couldn't you also just reverse every Element of the array, combine it with the original array, remove those that consist only of the same chars, and check for duplicates? I'm probably missing something, but that would be O(n)?:D

[Ben Pereira]

So here it's I believe would be:

class Solution {
    public int maximumNumberOfStringPairs(String[] words) {

        // get words in a list without the strings with two equal characters
        List<String> wordsList = Arrays.stream(words)
            .filter(w -> !(w.charAt(0)==w.charAt(1)))
            .collect(Collectors.toList());

        System.out.println(wordsList);

        // reverse it
        List<String> wReversedList = wordsList.stream().map(w -> new StringBuilder()
                                                            .append(w.charAt(1))
                                                            .append(w.charAt(0))
                                                            .toString()).collect(Collectors.toList());

        // remove what's not distinct
        wordsList.removeAll(wReversedList);

        // get distinct pairs (if after removal they are the same is zero, otherwise is the difference / 2)
        return wReversedList.size()==wordsList.size() ? 0 : (wReversedList.size() - wordsList.size())/2;
    }
}

Runtime: 15 ms, faster than 9.38% of Java online submissions for Find Maximum Number of String Pairs.

Memory Usage: 43.1 MB, less than 47.69% of Java online submissions for Find Maximum Number of String Pairs.

In this case because of many operations it doesn't look much doable. Let me know your thoughts on this, cheers.

[Ben Pereira]

That might be a way as well, I thought that I would have to do an extra check for duplicates with same chars but it's not needed since is distinct strings. :)
Let me try and update this post with the results, thanks.