LeetCode 1177 - Can Make Palindrome from Substring

The problem asks us to determine whether certain substrings of a given string s can be rearranged and partially modified to form a palindrome. A palindrome is a string that reads the same forward and backward.

leetcodemediumarrayhash-tablestringbit-manipulationprefix-sum

LeetCode Problem 1177

Difficulty: 🟡 Medium
Topics: Array, Hash Table, String, Bit Manipulation, Prefix Sum

Solution

Problem Understanding

The problem asks us to determine whether certain substrings of a given string s can be rearranged and partially modified to form a palindrome. A palindrome is a string that reads the same forward and backward. For each query [lefti, righti, ki], we are allowed to take the substring s[lefti...righti], rearrange its characters in any order, and replace up to ki characters with any lowercase letter. We then need to check if the resulting substring can be a palindrome.

The input consists of the string s and a list of queries. Each query gives the start and end indices of the substring and the maximum number of character replacements allowed. The output is a boolean array where each element indicates whether the corresponding substring can be transformed into a palindrome.

Constraints indicate that s and queries can be very large, up to 10^5 elements. This rules out naive solutions that examine each substring character by character or attempt all permutations. Edge cases include substrings of length 1, substrings with all identical letters, and queries with ki equal to zero.

The core challenge is efficiently determining, for any substring, how many characters would need to be changed to form a palindrome without explicitly rearranging or iterating over the substring each time.

Approaches

Brute Force

The brute-force solution would extract each substring for every query, count the occurrences of each character, and check if a palindrome is possible given ki. For a palindrome, at most one character can appear an odd number of times. We would compute how many characters have odd counts and see if ki is sufficient to convert enough of them to even counts. This approach is correct but extremely slow, since counting character frequencies for each substring takes O(n) time per query, resulting in O(n * q) complexity.

Optimal Approach

The optimal approach leverages prefix bitmasks to track character counts efficiently. Each letter a-z can be represented as a bit in a 26-bit integer. XOR operations allow us to compute the character count parity for any substring in constant time using a prefix array. A palindrome can tolerate at most one character with an odd count per half-length of the substring. We check if the number of odd-count characters divided by 2 is less than or equal to ki.

This approach avoids substring iteration and reduces the complexity from O(n * q) to O(n + q), which is feasible for the input size.

Approach Time Complexity Space Complexity Notes
Brute Force O(n * q) O(26) per query Count character frequencies for each substring
Optimal O(n + q) O(n) Use prefix bitmasks and XOR to compute odd counts efficiently

Algorithm Walkthrough

  1. Initialize a prefix array prefix_mask of size len(s)+1 where prefix_mask[i] stores a 26-bit integer representing the parity of character counts for s[0...i-1]. Each bit corresponds to a letter: 1 if the count is odd, 0 if even.
  2. Iterate through the string s. For each character c at index i, update prefix_mask[i+1] = prefix_mask[i] ^ (1 << (ord(c) - ord('a'))). This XOR operation flips the corresponding bit, tracking the parity of occurrences.
  3. For each query [l, r, k], calculate the substring bitmask mask = prefix_mask[r+1] ^ prefix_mask[l]. The XOR cancels out characters outside the substring, leaving only the odd/even counts for s[l...r].
  4. Count the number of set bits in mask using a population count function. Each set bit corresponds to a character with an odd count.
  5. Compute needed_replacements = odd_count // 2. This represents the minimum number of changes needed to make the substring a palindrome, since two odd-count characters can be fixed with one replacement.
  6. If needed_replacements <= k, append True to the answer array; otherwise, append False.

Why it works: The XOR-based prefix array encodes parity information for each prefix of the string. Substring XORs isolate the odd-count letters, allowing a constant-time check for each query. Palindromes require at most one odd character for odd-length strings, and even-length strings require all even counts. Dividing the odd count by 2 correctly accounts for pairwise transformations needed.

Python Solution

from typing import List

class Solution:
    def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:
        n = len(s)
        prefix_mask = [0] * (n + 1)
        
        for i in range(n):
            prefix_mask[i + 1] = prefix_mask[i] ^ (1 << (ord(s[i]) - ord('a')))
        
        result = []
        for l, r, k in queries:
            mask = prefix_mask[r + 1] ^ prefix_mask[l]
            odd_count = bin(mask).count('1')
            result.append(odd_count // 2 <= k)
        
        return result

In this implementation, prefix_mask tracks parity for each character using a 26-bit integer. XOR operations efficiently compute substring parities. The population count gives the number of odd characters, and dividing by 2 determines the required replacements. The final boolean is appended to the result for each query.

Go Solution

func canMakePaliQueries(s string, queries [][]int) []bool {
    n := len(s)
    prefixMask := make([]int, n+1)
    
    for i := 0; i < n; i++ {
        prefixMask[i+1] = prefixMask[i] ^ (1 << (s[i] - 'a'))
    }
    
    result := make([]bool, len(queries))
    for i, q := range queries {
        l, r, k := q[0], q[1], q[2]
        mask := prefixMask[r+1] ^ prefixMask[l]
        oddCount := 0
        for mask > 0 {
            oddCount += mask & 1
            mask >>= 1
        }
        result[i] = oddCount/2 <= k
    }
    
    return result
}

The Go implementation mirrors the Python logic, using an integer slice for prefix masks. Population count is performed manually using bitwise operations since Go lacks a built-in bin().count('1').

Worked Examples

For s = "abcda" and queries = [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]]:

Query Substring Mask (binary) Odd count Needed replacements Result
[3,3,0] "d" 0001000 1 0 True
[1,2,0] "bc" 0110 2 1 False
[0,3,1] "abcd" 1111 4 2 False
[0,3,2] "abcd" 1111 4 2 True
[0,4,1] "abcda" 11101 3 1 True

Complexity Analysis

Measure Complexity Explanation
Time O(n + q) O(n) to compute prefix masks, O(q) to process queries
Space O(n) Store prefix mask for each character position

The linear time complexity allows the solution to handle the maximum constraints efficiently, while space scales linearly with the input string length.

Test Cases

# Provided examples
assert Solution().canMakePaliQueries("abcda", [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]]) == [True, False, False, True, True]
assert Solution().canMakePaliQueries("lyb", [[0,1,0],[2,2,1]]) == [False, True]

# Edge cases
assert Solution().canMakePaliQueries("a", [[0,0,0]]) == [True]  # Single letter is always palindrome
assert Solution().canMakePaliQueries("aa", [[0,1,0]]) == [True]  # Already palindrome
assert Solution().canMakePaliQueries("ab", [[0,1,0]]) == [False]  # Needs 1 replacement, ki=0
assert Solution().canMakePaliQueries("abcd", [[0,3,2]]) == [True]  # Needs 2 replacements
assert Solution().canMakePaliQueries("abcd", [[0,3,1]]) == [False]  # Not enough replacements
Test Why
Single letter Minimal case, trivially palindrome
Two identical letters Already palindrome, no replacement needed
Two different letters, ki=0 Cannot become palindrome
Substring longer, ki sufficient Tests correct counting of needed replacements
Substring longer, ki insufficient Verifies handling when replacements are insufficient

Edge Cases

  1. Single-character substring: Any single character is trivially a palindrome. Implementation handles this correctly because odd_count = 1, `needed_replacements