Maximum Palindromes After Operations - Practice Coding Problems

Maximum Palindromes After Operations - Problem

Array Hash Table String Greedy Sorting Counting Medium

You are given a 0-indexed string array words having length n and containing 0-indexed strings.

You are allowed to perform the following operation any number of times (including zero):

Choose integers i, j, x, and y such that 0 <= i, j < n, 0 <= x < words[i].length, 0 <= y < words[j].length, and swap the characters words[i][x] and words[j][y].

Return an integer denoting the maximum number of palindromes words can contain, after performing some operations.

Note: i and j may be equal during an operation.

Input & Output

Example 1 — Basic Case

$ Input: words = ["abc","car","a"]

› Output: 2

💡 Note: We have characters: a,b,c,c,a,r,a → {a:3, b:1, c:2, r:1}. Pairs=3, odds=1. Words sorted by length: [3,3,1]. First two words need 1 pair each, so we can form 2 palindromes like "aca" and "rcr".

Example 2 — All Same Length

$ Input: words = ["ab","ty","yt"]

› Output: 2

💡 Note: Characters: a,b,t,y,y,t → {a:1, b:1, t:2, y:2}. Pairs=2, odds=2. Each word needs 1 pair. We can form 2 palindromes like "ty" and "yt", but "ab" cannot be formed into palindrome with remaining characters.

Example 3 — Single Character Words

$ Input: words = ["a","b","a"]

› Output: 2

💡 Note: Characters: a,b,a → {a:2, b:1}. Pairs=1, odds=1. All words have length 1 (need 0 pairs each). We can form 2 palindromes using the 2 'a' characters, but 'b' forms the third palindrome too. Total: 3, but wait - we have 2 odds available, so answer is 2.

Constraints

1 ≤ words.length ≤ 10⁵
1 ≤ words[i].length ≤ 10⁵
sum(words[i].length) ≤ 2 × 10⁵
words[i] consists of lowercase English letters only

Visualization

Tap to expand

Understanding the Visualization

Input Words

Array of strings with swappable characters

Global Pool

All characters can be redistributed freely

Form Palindromes

Maximum palindromes using optimal character assignment

Key Takeaway

🎯 Key Insight: Since characters can be swapped freely, use greedy assignment by word length to maximize palindromes

Asked in

G Google 15 M Microsoft 12

The key insight is that we can swap any characters freely, so treat all characters as a global pool. Count character frequencies, calculate available pairs, then greedily assign pairs to longest words first. Time: O(n log n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Try All Distributions	O(k!)	O(k)	Generate all possible character distributions and count maximum palindromes
Greedy Character Assignment	O(n log n + k)	O(1)	Sort words by length and greedily assign character pairs from global pool

Try All Distributions — Algorithm Steps

Step 1: Generate all possible ways to distribute characters
Step 2: For each distribution, check if words can form palindromes
Step 3: Return maximum count found

Visualization

Tap to expand

Step-by-Step Walkthrough

All Characters

Collect all available characters from input words

Try Distributions

Attempt different ways to assign characters to words

Count Palindromes

For each distribution, count how many palindromes can be formed

Code -

solution.c — C

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

#define MAX_WORDS 1000
#define MAX_WORD_LEN 100
#define MAX_CHARS 256

int compare_desc(const void *a, const void *b) {
    return (*(int*)b - *(int*)a);
}

int solution(char words[][MAX_WORD_LEN], int wordCount) {
    if (wordCount == 0) return 0;
    
    int charCount[MAX_CHARS] = {0};
    
    // Count all characters
    for (int i = 0; i < wordCount; i++) {
        for (int j = 0; words[i][j] != '\0'; j++) {
            charCount[(unsigned char)words[i][j]]++;
        }
    }
    
    int pairs = 0, odds = 0;
    for (int i = 0; i < MAX_CHARS; i++) {
        if (charCount[i] > 0) {
            pairs += charCount[i] / 2;
            odds += charCount[i] % 2;
        }
    }
    
    int wordLengths[MAX_WORDS];
    for (int i = 0; i < wordCount; i++) {
        wordLengths[i] = strlen(words[i]);
    }
    qsort(wordLengths, wordCount, sizeof(int), compare_desc);
    
    int palindromes = 0;
    for (int i = 0; i < wordCount; i++) {
        int neededPairs = wordLengths[i] / 2;
        if (pairs >= neededPairs) {
            palindromes++;
            pairs -= neededPairs;
            if (wordLengths[i] % 2 == 1 && odds > 0) {
                odds--;
            }
        }
    }
    
    return palindromes;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple JSON array parsing
    char words[MAX_WORDS][MAX_WORD_LEN];
    int wordCount = 0;
    
    char *ptr = strchr(line, '[');
    if (ptr) {
        ptr++;
        char *token = strtok(ptr, ",]");
        while (token && wordCount < MAX_WORDS) {
            // Remove quotes and spaces
            while (*token == ' ' || *token == '"') token++;
            char *end = token + strlen(token) - 1;
            while (end > token && (*end == ' ' || *end == '"' || *end == ']')) {
                *end = '\0';
                end--;
            }
            if (strlen(token) > 0) {
                strcpy(words[wordCount], token);
                wordCount++;
            }
            token = strtok(NULL, ",]");
        }
    }
    
    int result = solution(words, wordCount);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(k!)

k! permutations where k is total character count

✓ Linear Growth

Space Complexity

O(k)

Storage for current distribution attempt

✓ Linear Space

12.5K Views

Medium Frequency

~25 min Avg. Time

234 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

Try All Distributions — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler