Find Maximum Number of String Pairs

This approach iterates through all possible pairs of strings in the array and checks if they form a valid pair. A pair is valid if one string is the reverse of the other. To ensure each string is part of at most one pair, we use a boolean array to mark strings that have already been matched.

• Initialize a counter pairs to 0.
• Create a boolean array used of the same size as words, initialized to false. This will track which strings have already been paired.
• Use a nested loop to iterate through all pairs of indices (i, j) such that 0 <= i < j < words.length.
• In the outer loop, if used[i] is true, skip to the next i.
• In the inner loop, if used[j] is true, skip to the next j.
• For each pair (words[i], words[j]), check if words[i] is the reverse of words[j]. Since string length is 2, this means checking if words[i].charAt(0) == words[j].charAt(1) and words[i].charAt(1) == words[j].charAt(0).
• If they form a pair, increment the pairs counter, mark both strings as used (used[i] = true, used[j] = true), and break the inner loop to find a pair for the next i.
• Return the final pairs count.

We can solve this problem by systematically comparing every string with every other string that comes after it in the array.

We initialize a counter for the number of pairs to zero. To avoid pairing a string more than once, we use a boolean array, used, to keep track of which strings have already been included in a pair.

We use a nested loop. The outer loop iterates from i = 0 to n-1 (where n is the number of words), and the inner loop iterates from j = i + 1 to n-1. This structure ensures we only consider pairs (words[i], words[j]) where i < j.

Inside the loops, if both words[i] and words[j] have not been used yet, we check if words[i] is the reverse of words[j]. Since each string has a length of 2, reversing words[i] (e.g., "ab") is straightforward: we swap its two characters to get the reversed string (e.g., "ba").

If words[j] matches the reversed words[i], we've found a pair. We increment our pair counter and mark both words[i] and words[j] as used by setting used[i] and used[j] to true. We then break the inner loop for the current i because words[i] has found its unique partner.

After checking all possible pairs, the value of the counter is the maximum number of pairs.

class Solution {
    public int maximumNumberOfStringPairs(String[] words) {
        int n = words.length;
        int count = 0;
        boolean[] used = new boolean[n];

        for (int i = 0; i < n; i++) {
            if (used[i]) {
                continue;
            }
            for (int j = i + 1; j < n; j++) {
                if (used[j]) {
                    continue;
                }
                String s1 = words[i];
                String s2 = words[j];
                // Since length is 2, reversing is just swapping characters.
                if (s1.charAt(0) == s2.charAt(1) && s1.charAt(1) == s2.charAt(0)) {
                    count++;
                    used[i] = true;
                    used[j] = true;
                    break; // words[i] is now paired, move to the next i
                }
            }
        }
        return count;
    }
}