2744. Find Maximum Number of String Pairs Solution

The 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 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 0^th string with the 2^nd string, as the reversed string of word[0] is "dc" and is equal to words[2].
- We pair the 1^st string with the 3^rd 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 0^th string with the 1^st 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.

Approach overview

Problem Overview: You are given an array of two‑character strings. A valid pair exists when one string is the reverse of another string in the array (for example, "ab" and "ba"). The goal is to count the maximum number of such disjoint pairs.

Approach 1: Brute Force Pair Checking (O(n²) time, O(1) space)

The direct method compares every string with every other string. Iterate through the array using two nested loops. For each string words[i], compute its reverse and check if it matches any words[j] where j > i. If a match is found, count the pair and ensure those indices are not reused. This approach relies only on basic iteration and string comparison, making it useful for understanding the core requirement of the problem. However, because it performs pairwise comparisons across the array, the time complexity grows quadratically as the input size increases.

Even though the brute force method works within constraints for small inputs, it becomes inefficient when the number of strings increases. The algorithm performs repeated reverse checks and comparisons, which makes it a good baseline but not the best choice when an optimized lookup structure is available.

Approach 2: Hash Map for Quick Lookups (O(n) time, O(n) space)

A more efficient solution uses a hash-based structure to track strings you've already seen. Iterate through the array once. For each string, compute its reversed form (for example, "ab" → "ba"). Before storing the current string, check whether the reversed string already exists in the hash map or hash set. If it does, you found a valid pair, so increment the pair count and remove the stored string to avoid reuse.

This works because a hash lookup runs in constant time on average. Instead of comparing against every other element, you immediately determine whether the complementary reversed string exists. Each string is processed once, making the total runtime linear relative to the number of elements.

The approach is a common pattern in problems involving complements or reverse matching. The hash structure acts as a memory of previously seen elements and eliminates redundant comparisons. Problems involving string transformations often combine hash table lookups with simple string operations while iterating through an array.

Recommended for interviews: Start by explaining the brute force method to demonstrate that you understand the definition of a valid pair. Then move to the hash map approach, which reduces the runtime from quadratic to linear. Interviewers usually expect the hash-based solution because it shows awareness of efficient lookups and common optimization patterns.

Approach 1: Approach 1: Brute Force Pair Checking

This approach involves iterating through each possible pair of strings in the array and checking if one is the reverse of the other. Given the constraints (with length at most 50), a simple nested loop can be employed to compare each string with every other string for reversibility.

Though this method isn't the most efficient due to its O(n^2) complexity, it is straightforward and easy to implement, especially given the manageable input size limit.

Python

def max_pairs(words):
    n = len(words)
    count = 0
    used = [False] * n
    for i in range(n):
        if used[i]:
            continue
        for j in range(i + 1, n):
            if not used[j] and words[i] == words[j][::-1]:
                count += 1
                used[i] = used[j] = True
                break
    return count

words = ["cd", "ac", "dc", "ca", "zz"]
print(max_pairs(words))

Java

import java.util.*;

public class MaxPairs {
    public static boolean isReverse(String a, String b) {
        return a.charAt(0) == b.charAt(1) && a.charAt(1) == b.charAt(0);
    }

    public static int maxPairs(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] && isReverse(words[i], words[j])) {
                    count++;
                    used[i] = used[j] = true;
                    break;
                }
            }
        }
        return count;
    }

    public static void main(String[] args) {
        String[] words = {"cd", "ac", "dc", "ca", "zz"};
        System.out.println(maxPairs(words));
    }
}

C++

#include <iostream>
#include <vector>
#include <string>
using namespace std;

bool isReverse(const string &a, const string &b) {
    return a[0] == b[1] && a[1] == b[0];
}

int maxPairs(vector<string> &words) {
    int n = words.size();
    int count = 0;
    vector<bool> used(n, false);
    for (int i = 0; i < n; ++i) {
        if (used[i]) continue;
        for (int j = i + 1; j < n; ++j) {
            if (!used[j] && isReverse(words[i], words[j])) {
                count++;
                used[i] = used[j] = true;
                break;
            }
        }
    }
    return count;
}

int main() {
    vector<string> words = {"cd", "ac", "dc", "ca", "zz"};
    cout << maxPairs(words) << endl;
    return 0;
}

JavaScript

function maxPairs(words) {
    let n = words.length;
    let count = 0;
    let used = new Array(n).fill(false);

    for (let i = 0; i < n; i++) {
        if (used[i]) continue;
        for (let j = i + 1; j < n; j++) {
            if (!used[j] && words[i] === words[j].split('').reverse().join('')) {
                count++;
                used[i] = used[j] = true;
                break;
            }
        }
    }

    return count;
}

let words = ["cd", "ac", "dc", "ca", "zz"];
console.log(maxPairs(words));

#include <stdio.h>
#include <string.h>

int isReverse(char *word1, char *word2) {
    return word1[0] == word2[1] && word1[1] == word2[0];
}

int maxPairs(char **words, int wordsSize) {
    int count = 0;
    int used[50] = {0};
    for(int i = 0; i < wordsSize; i++) {
        for(int j = i + 1; j < wordsSize; j++) {
            if(!used[i] && !used[j] && isReverse(words[i], words[j])) {
                count++;
                used[i] = used[j] = 1;
                break;
            }
        }
    }
    return count;
}

int main() {
    char *words[] = {"cd", "ac", "dc", "ca", "zz"};
    int size = sizeof(words) / sizeof(words[0]);
    printf("%d\n", maxPairs(words, size));
    return 0;
}

using System;
using System.Collections.Generic;

class MaxPairs {
    public static bool IsReverse(string a, string b) {
        return a[0] == b[1] && a[1] == b[0];
    }
    
    public static int MaxPairsMethod(string[] words) {
        int n = words.Length;
        int count = 0;
        bool[] used = new bool[n];
        for (int i = 0; i < n; ++i) {
            if (used[i]) continue;
            for (int j = i + 1; j < n; ++j) {
                if (!used[j] && IsReverse(words[i], words[j])) {
                    count++;
                    used[i] = used[j] = true;
                    break;
                }
            }
        }
        return count;
    }

    public static void Main(string[] args) {
        string[] words = {"cd", "ac", "dc", "ca", "zz"};
        Console.WriteLine(MaxPairsMethod(words));
    }
}

This Python function iterates over the list of words with nested loops. It checks for reversibility by reversing one string and comparing it to another. A list maintains whether a word has been paired to prevent reuse.

Complexity

Time Complexity: O(n^2).

Space Complexity: O(n).

Try this approach in the editor

Approach 2: Approach 2: Hash Map for Quick Lookups

Instead of checking each pair naively, we can use a hash map to store each word and perform reverse checks for faster lookups. This allows us to efficiently determine if a word's reverse exists among the previously seen words, effectively reducing unnecessary comparisons.

This approach leverages the hash map's average constant time complexity for lookups to enhance performance over the brute force method.

Python

def max_pairs_using_map(words):
    used = {}
    count = 0
    for word in words:
        rev = word[::-1]
        if rev in used and not used[rev]:
            count += 1
            used[rev] = True
        else:
            used[word] = False
    return count

words = ["cd", "ac", "dc", "ca", "zz"]
print(max_pairs_using_map(words))

Java

import java.util.HashMap;

public class MaxPairsUsingMap {
    public static int maxPairsUsingMap(String[] words) {
        HashMap<String, Boolean> used = new HashMap<>();
        int count = 0;
        for (String word : words) {
            String rev = new StringBuilder(word).reverse().toString();
            if (used.containsKey(rev) && !used.get(rev)) {
                count++;
                used.put(rev, true);
            } else {
                used.put(word, false);
            }
        }
        return count;
    }

    public static void main(String[] args) {
        String[] words = { "cd", "ac", "dc", "ca", "zz" };
        System.out.println(maxPairsUsingMap(words));
    }
}

C++

#include <iostream>
#include <vector>
#include <unordered_map>

int maxPairsUsingMap(std::vector<std::string> &words) {
    std::unordered_map<std::string, bool> used;
    int count = 0;
    for (std::string &word : words) {
        std::string rev = {word[1], word[0]};
        if (used.count(rev) && !used[rev]) {
            count++;
            used[rev] = true;
        } else {
            used[word] = false;
        }
    }
    return count;
}

int main() {
    std::vector<std::string> words = {"cd", "ac", "dc", "ca", "zz"};
    std::cout << maxPairsUsingMap(words) << std::endl;
    return 0;
}

JavaScript

function maxPairsUsingMap(words) {
    const used = {};
    let count = 0;

    words.forEach(word => {
        const rev = word.split('').reverse().join('');
        if (used[rev] !== undefined && !used[rev]) {
            count++;
            used[rev] = true;
        } else {
            used[word] = false;
        }
    });

    return count;
}

const words = ["cd", "ac", "dc", "ca", "zz"];
console.log(maxPairsUsingMap(words));

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

#define MAX_WORDS 50

int maxPairsUsingMap(char **words, int wordsSize) {
    bool used[MAX_WORDS] = {0};
    int count = 0;
    for (int i = 0; i < wordsSize; i++) {
        if (used[i]) continue;
        char rev[3];
        rev[0] = words[i][1];
        rev[1] = words[i][0];
        rev[2] = '\0';
        for (int j = 0; j < wordsSize; j++) {
            if (i != j && !used[j] && strcmp(rev, words[j]) == 0) {
                count++;
                used[i] = used[j] = true;
                break;
            }
        }
    }
    return count;
}

int main() {
    char *words[] = {"cd", "ac", "dc", "ca", "zz"};
    int size = sizeof(words) / sizeof(words[0]);
    printf("%d\n", maxPairsUsingMap(words, size));
    return 0;
}

using System;
using System.Collections.Generic;

class MaxPairsUsingMap {
    public static int MaxPairsMethod(string[] words) {
        Dictionary<string, bool> used = new Dictionary<string, bool>();
        int count = 0;
        foreach (var word in words) {
            var rev = new string(new[] { word[1], word[0] });
            if (used.ContainsKey(rev) && !used[rev]) {
                count++;
                used[rev] = true;
            } else {
                used[word] = false;
            }
        }
        return count;
    }

    public static void Main(string[] args) {
        string[] words = {"cd", "ac", "dc", "ca", "zz"};
        Console.WriteLine(MaxPairsMethod(words));
    }
}

This Python strategy employs a dictionary to oversee paired status, providing a swift association with each word matching its reverse among previously mapped entries, notably projected via dictionary key operations.

Complexity

Time Complexity: O(n).

Space Complexity: O(n).

Try this approach in the editor

Approach 3: Hash Table

We can use a hash table cnt to store the number of occurrences of each reversed string in the array words.

We iterate through the array words. For each string w, we add the number of occurrences of its reversed string to the answer, then increment the count of w by 1.

Finally, we return the answer.

The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array words.

TypeScript

function maximumNumberOfStringPairs(words: string[]): number {
    const cnt: { [key: number]: number } = {};
    let ans = 0;
    for (const w of words) {
        const [a, b] = [w.charCodeAt(0) - 97, w.charCodeAt(w.length - 1) - 97];
        ans += cnt[(b << 5) | a] || 0;
        cnt[(a << 5) | b] = (cnt[(a << 5) | b] || 0) + 1;
    }
    return ans;
}

func maximumNumberOfStringPairs(words []string) (ans int) {
	cnt := map[int]int{}
	for _, w := range words {
		a, b := int(w[0]-'a'), int(w[1]-'a')
		ans += cnt[b<<5|a]
		cnt[a<<5|b]++
	}
	return
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Approach 1: Brute Force Pair Checking	Time Complexity: O(n^2). Space Complexity: O(n).
Approach 2: Hash Map for Quick Lookups	Time Complexity: O(n). Space Complexity: O(n).
Hash Table	–

Approach

Complexity

Approach 1: Brute Force Pair Checking

Time Complexity: O(n^2).

Space Complexity: O(n).

Approach 2: Hash Map for Quick Lookups

Time Complexity: O(n).

Space Complexity: O(n).

Hash Table

–

Complexity analysis

Approach	Time	Space	When to Use
Brute Force Pair Checking	O(n²)	O(1)	Small input sizes or when demonstrating the baseline logic during interviews
Hash Map for Quick Lookups	O(n)	O(n)	General case and interview‑expected solution using constant‑time lookups

Frequently asked questions

Is Find Maximum Number of String Pairs easy or hard?

Find Maximum Number of String Pairs is categorized as an Easy problem. The main concept is recognizing reversed string pairs and using a hash table to avoid unnecessary comparisons, which makes the optimized solution straightforward.

Find Maximum Number of String Pairs Python/Java solution

In Python, you typically use a set to track seen strings and check for reversed matches in O(1) average time. In Java, the same logic is implemented using a HashSet or HashMap. Both implementations follow the same algorithm: reverse the string, check for existence, and update the pair count.

How to solve Find Maximum Number of String Pairs in O(n)?

Iterate through the array once and maintain a hash set of seen strings. For each string, generate its reversed version and check if it already exists in the set. If found, increment the pair count and remove the matched string; otherwise, insert the current string. This ensures each string participates in at most one pair.

What is the best approach for Find Maximum Number of String Pairs?

The most efficient approach uses a hash map or hash set to store previously seen strings. For each word, compute its reversed string and check if that reversed version already exists in the hash structure. This reduces the search from comparing every pair to a constant‑time lookup, giving O(n) time complexity and O(n) space complexity.

Is Find Maximum Number of String Pairs asked at Google/Amazon/Meta?

Problems involving hash maps and reverse string matching appear frequently in interviews at companies like Amazon, Google, and Meta. While this exact question may vary, the underlying pattern of using hash tables for quick complement lookups is common in coding interviews.

What data structure is used in Find Maximum Number of String Pairs?

The optimal solution uses a hash table structure such as a HashSet or HashMap. It enables constant‑time average lookup to check whether the reverse of a string has already been encountered while iterating through the array.

What is the time complexity of Find Maximum Number of String Pairs?

The brute force approach runs in O(n^2) time because every string is compared with every other string. The optimized hash table solution runs in O(n) time since each string is processed once and reverse lookups occur in constant time on average.

Find Maximum Number of String Pairs solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Brute Force Pair Checking

Approach 2: Approach 2: Hash Map for Quick Lookups

Approach 3: Hash Table

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Find Maximum Number of String Pairs solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Brute Force Pair Checking

Approach 2: Approach 2: Hash Map for Quick Lookups

Approach 3: Hash Table

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems