Problem

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 _themaximum number of pairs that can be formed from the array _words .

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

Examples

Example 1

1
2
3
4
5
6

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

1
2
3
4
5

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

1
2
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.

Solution

Method 1 – Hash Set for Reverse Lookup

Intuition

We want to pair each string with its reverse, but each string can be used at most once. By using a set to track available strings, we can efficiently check for reverse pairs.

Approach

  1. Initialize a set with all words.
  2. Iterate through each word:
    • If the word is still in the set and its reverse is also in the set (and not the same word), count a pair and remove both from the set.
    • If the word is a palindrome, only count it if there are at least two copies (not possible here since all words are distinct).
  3. Return the total number of pairs found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
public:
    int maximumNumberOfStringPairs(vector<string>& words) {
        unordered_set<string> st(words.begin(), words.end());
        int ans = 0;
        for (auto& w : words) {
            string rev = w;
            reverse(rev.begin(), rev.end());
            if (st.count(w) && st.count(rev) && w != rev) {
                ans++;
                st.erase(w);
                st.erase(rev);
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

func maximumNumberOfStringPairs(words []string) int {
    st := make(map[string]bool)
    for _, w := range words {
        st[w] = true
    }
    ans := 0
    for _, w := range words {
        rev := reverse(w)
        if st[w] && st[rev] && w != rev {
            ans++
            st[w] = false
            st[rev] = false
        }
    }
    return ans
}
func reverse(s string) string {
    b := []byte(s)
    for i, j := 0, len(b)-1; i < j; i, j = i+1, j-1 {
        b[i], b[j] = b[j], b[i]
    }
    return string(b)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    public int maximumNumberOfStringPairs(String[] words) {
        Set<String> st = new HashSet<>(Arrays.asList(words));
        int ans = 0;
        for (String w : words) {
            String rev = new StringBuilder(w).reverse().toString();
            if (st.contains(w) && st.contains(rev) && !w.equals(rev)) {
                ans++;
                st.remove(w);
                st.remove(rev);
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    fun maximumNumberOfStringPairs(words: Array<String>): Int {
        val st = words.toMutableSet()
        var ans = 0
        for (w in words) {
            val rev = w.reversed()
            if (w != rev && w in st && rev in st) {
                ans++
                st.remove(w)
                st.remove(rev)
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def maximumNumberOfStringPairs(self, words: list[str]) -> int:
        st = set(words)
        ans = 0
        for w in words:
            rev = w[::-1]
            if w != rev and w in st and rev in st:
                ans += 1
                st.remove(w)
                st.remove(rev)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

impl Solution {
    pub fn maximum_number_of_string_pairs(words: Vec<String>) -> i32 {
        use std::collections::HashSet;
        let mut st: HashSet<String> = words.iter().cloned().collect();
        let mut ans = 0;
        for w in &words {
            let rev: String = w.chars().rev().collect();
            if w != &rev && st.contains(w) && st.contains(&rev) {
                ans += 1;
                st.remove(w);
                st.remove(&rev);
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    maximumNumberOfStringPairs(words: string[]): number {
        const st = new Set(words);
        let ans = 0;
        for (const w of words) {
            const rev = w.split('').reverse().join('');
            if (w !== rev && st.has(w) && st.has(rev)) {
                ans++;
                st.delete(w);
                st.delete(rev);
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n * k), where n is the number of words and k is the average word length. Each word and its reverse are checked once.
  • 🧺 Space complexity: O(n * k), for storing the set of words.