Can Make Palindrome from Substring - Practice Coding Problems

Can Make Palindrome from Substring - Problem

Array Hash Table String Bit Manipulation Prefix Sum Medium

You are given a string s and array queries where queries[i] = [left_i, right_i, k_i]. We may rearrange the substring s[left_i...right_i] for each query and then choose up to k_i of them to replace with any lowercase English letter.

If the substring is possible to be a palindrome string after the operations above, the result of the query is true. Otherwise, the result is false.

Return a boolean array answer where answer[i] is the result of the i-th query queries[i].

Note: Each letter is counted individually for replacement, so if s[left_i...right_i] = "aaa" and k_i = 2, we can only replace two of the letters. Also, no query modifies the initial string s.

Input & Output

Example 1 — Multiple Query Types

$ Input: s = "abcda", queries = [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]]

› Output: [true,false,false,true,true]

💡 Note: Query [3,3,0]: substring "d" is already palindrome. Query [1,2,0]: "bc" needs 1 replacement, but k=0. Query [0,3,1]: "abcd" has 4 odd chars, needs 1.5≈2 replacements > k=1. Query [0,3,2]: "abcd" needs 2 replacements ≤ k=2. Query [0,4,1]: "abcda" has 2 odd chars (b,c), needs 0.5≈1 replacement ≤ k=1.

Example 2 — Edge Cases

$ Input: s = "lyb", queries = [[0,1,0],[2,2,1]]

› Output: [false,true]

💡 Note: Query [0,1,0]: "ly" has 2 odd characters, needs 1 replacement but k=0. Query [2,2,1]: "b" is single character, always palindrome.

Example 3 — All Same Characters

$ Input: s = "aaaa", queries = [[0,3,0],[1,2,1]]

› Output: [true,true]

💡 Note: Query [0,3,0]: "aaaa" has all even frequencies, palindrome possible. Query [1,2,1]: "aa" is already palindrome.

Constraints

1 ≤ s.length, queries.length ≤ 10⁵
0 ≤ left_i ≤ right_i < s.length
0 ≤ k_i ≤ s.length
s consists of lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input

String with query ranges and replacement limits

Process

Count odd-frequency characters in each substring

Output

Boolean array indicating palindrome possibility

Key Takeaway

🎯 Key Insight: A palindrome can have at most one character with odd frequency

Asked in

G Google 25 f Facebook 18 a Amazon 12

The key insight is that a palindrome can have at most one character with odd frequency. We can use prefix sums or bit manipulation to efficiently count character frequencies in substrings. Best approach uses XOR prefix arrays for O(1) queries. Time: O(n + q), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(q × n)	O(1)	For each query, count character frequencies in substring
Prefix Sum with Frequency	O(n + q)	O(26n)	Pre-compute character frequencies for efficient range queries
Bit Manipulation Optimization	O(n + q)	O(n)	Use bitmask to track odd character frequencies efficiently

Brute Force — Algorithm Steps

For each query, extract substring
Count frequency of each character
Count characters with odd frequency
Check if (odd_count - 1) / 2 <= k

Visualization

Tap to expand

Step-by-Step Walkthrough

Extract Substring

Get substring for current query

Count Frequencies

Count each character in substring

Check Palindrome

Determine if palindrome possible with k replacements

Code -

solution.c — C

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

void solution(char* s, int queries[][3], int queryCount, int* result) {
    for (int i = 0; i < queryCount; i++) {
        int left = queries[i][0];
        int right = queries[i][1];
        int k = queries[i][2];
        
        // Count character frequencies
        int freq[26] = {0};
        for (int j = left; j <= right; j++) {
            freq[s[j] - 'a']++;
        }
        
        // Count characters with odd frequency
        int oddCount = 0;
        for (int j = 0; j < 26; j++) {
            if (freq[j] % 2 == 1) {
                oddCount++;
            }
        }
        
        // For palindrome, we need at most 1 odd frequency character
        int neededReplacements = (oddCount > 1) ? (oddCount - 1) / 2 : 0;
        
        result[i] = (neededReplacements <= k);
    }
}

int main() {
    char s[1001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    char queriesLine[10000];
    fgets(queriesLine, sizeof(queriesLine), stdin);
    
    // Simple parsing for the format [[a,b,c],[d,e,f],...]
    int queries[100][3];
    int queryCount = 0;
    
    char* ptr = queriesLine + 1; // Skip first '['
    while (*ptr != ']' && queryCount < 100) {
        if (*ptr == '[') {
            ptr++;
            queries[queryCount][0] = atoi(ptr);
            while (*ptr != ',') ptr++;
            ptr++;
            queries[queryCount][1] = atoi(ptr);
            while (*ptr != ',') ptr++;
            ptr++;
            queries[queryCount][2] = atoi(ptr);
            while (*ptr != ']') ptr++;
            ptr++;
            queryCount++;
        }
        ptr++;
    }
    
    int result[100];
    solution(s, queries, queryCount, result);
    
    printf("[");
    for (int i = 0; i < queryCount; i++) {
        printf("%s", result[i] ? "true" : "false");
        if (i < queryCount - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(q × n)

q queries, each processes up to n characters

✓ Linear Growth

Space Complexity

O(1)

Only uses frequency array of size 26

✓ Linear Space

28.5K Views

Medium Frequency

~35 min Avg. Time

892 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

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler