Find Maximum Number of String Pairs - Practice Coding Problems

Find Maximum Number of String Pairs - 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.

Input & Output

Example 1 — Basic Case

$ Input: words = ["lc","cl","gg"]

› Output: 1

💡 Note: The string "lc" can be paired with "cl" since "lc" equals the reverse of "cl". We have 1 pair.

Example 2 — Multiple Pairs

$ Input: words = ["ab","ba","cc"]

› Output: 1

💡 Note: "ab" can pair with "ba" (reverse match). "cc" is its own reverse but needs another "cc" to pair, so it remains unpaired. Total: 1 pair.

Example 3 — No Pairs

$ Input: words = ["aa","ab"]

› Output: 0

💡 Note: "aa" is palindrome but needs another "aa" to pair. "ab" would need "ba" but it doesn't exist. No pairs possible.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input

Array of distinct strings: ["lc","cl","gg"]

Find Pairs

Match strings with their reverses: lc ↔ cl

Count

Return maximum pairs possible: 1

Key Takeaway

🎯 Key Insight: Each string pairs only with its exact reverse - use hash map for efficient reverse lookups

Asked in

A Amazon 15 G Google 12

The key insight is that each string can only pair with its exact reverse. The optimal approach uses a hash map to store seen strings and check for reverse matches in O(1) time. Best approach: Hash Map with Time: O(n×m), Space: O(n×m).

Common Approaches

Approach	Time	Space	Notes
✓ Hash Map Optimization	O(n × m)	O(n × m)	Use hash map to store strings and check if their reverse exists
Brute Force	O(n² × m)	O(1)	Check every pair of strings to see if one is the reverse of the other

Hash Map Optimization — Algorithm Steps

Create empty hash map
For each string, check if its reverse exists in map
If exists, increment pairs and remove reverse from map
Otherwise, add current string to map

Visualization

Tap to expand

Step-by-Step Walkthrough

Check Map

For each string, check if its reverse exists in hash map

Pair Found

If reverse exists, count pair and remove from map

Add to Map

If no reverse, add current string to map

Code -

solution.c — C

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

#define MAX_WORDS 1000
#define MAX_LEN 100

void reverse_string(char* str, char* result) {
    int len = strlen(str);
    for (int i = 0; i < len; i++) {
        result[i] = str[len - 1 - i];
    }
    result[len] = '\0';
}

int find_in_set(char set[][MAX_LEN], int size, char* target) {
    for (int i = 0; i < size; i++) {
        if (strcmp(set[i], target) == 0) {
            return i;
        }
    }
    return -1;
}

void remove_from_set(char set[][MAX_LEN], int* size, int index) {
    for (int i = index; i < *size - 1; i++) {
        strcpy(set[i], set[i + 1]);
    }
    (*size)--;
}

int solution(char words[][MAX_LEN], int n) {
    char seen[MAX_WORDS][MAX_LEN];
    int seen_size = 0;
    int pairs = 0;
    char reversed[MAX_LEN];
    
    for (int i = 0; i < n; i++) {
        reverse_string(words[i], reversed);
        int index = find_in_set(seen, seen_size, reversed);
        if (index != -1) {
            pairs++;
            remove_from_set(seen, &seen_size, index);
        } else {
            strcpy(seen[seen_size], words[i]);
            seen_size++;
        }
    }
    
    return pairs;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    char words[MAX_WORDS][MAX_LEN];
    int n = 0;
    
    char* token = strtok(line, "[],\"\n");
    while (token != NULL && strlen(token) > 0) {
        if (token[0] != ' ' && token[0] != '\0') {
            strcpy(words[n], token);
            n++;
        }
        token = strtok(NULL, "[],\"\n");
    }
    
    int result = solution(words, n);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × m)

Single pass through n strings, each string reversal takes O(m) time

✓ Linear Growth

Space Complexity

O(n × m)

Hash map stores up to n strings, each of average length m

⚡ Linearithmic Space

12.5K Views

Medium Frequency

~15 min Avg. Time

324 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Hash Map Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler