We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Can Make Palindrome from Substring

Number: 1281

Difficulty: Medium

Paid? No

Companies: Akuna Capital

Problem Description

Given a string s and several queries, each defined by [left, right, k], determine if it is possible to rearrange the substring s[left...right] and then replace at most k characters so that it becomes a palindrome.

Key Insights

  • The key observation is that for a string to be rearranged into a palindrome, at most one character can have an odd frequency.
  • When characters appear an odd number of times, at least (oddCount // 2) replacements are needed (by pairing up unpaired characters) to form a palindrome.
  • Pre-computing a prefix frequency count (or using a bitmask to track parity) helps quickly determine the frequency counts in any substring.
  • For each query, calculate how many characters appear an odd number of times; if (oddCount//2) <= k, then the substring can be transformed into a palindrome.

Space and Time Complexity

Time Complexity: O(n + q), where n is the length of s and q is the number of queries. Preprocessing the prefix masks takes O(n) time and each query is answered in O(1). Space Complexity: O(n), for storing the prefix frequency (or bitmask) information.

Solution

We use a bitmask-based approach to track the parity (odd or even occurrence) of each letter in the string. Create a prefix array where each index i stores a bitmask representing the odd/even status of each letter from s[0] to s[i-1]. For a query [left, right, k], compute the bitmask difference (using XOR) between the prefix at right+1 and left. The number of bits that are set in this difference gives the count of characters with odd occurrences. To form a palindrome, at most one odd count is allowed, and each pair of extra odds needs to be fixed by a replacement, meaning we need (odd_count // 2) operations. If (odd_count // 2) <= k, the substring can be made into a palindrome after allowed modifications.

Code Solutions

# Python solution using prefix bit masks
def canMakePaliQueries(s, queries):
    n = len(s)
    # prefix_mask[i] will store the bitmask for the counts (parity) for s[0:i]
    prefix_mask = [0] * (n + 1)
    for i in range(n):
        # Compute mask for current letter (set the bit corresponding to letter position)
        curr_bit = 1 << (ord(s[i]) - ord('a'))
        prefix_mask[i+1] = prefix_mask[i] ^ curr_bit  # Toggle the bit
        
    result = []
    for left, right, k in queries:
        # XOR of prefix masks gives the difference mask for s[left:right+1]
        mask = prefix_mask[right+1] ^ prefix_mask[left]
        # Count number of bits set in mask (number of odd occurrences)
        odd_count = bin(mask).count("1")
        # Check if allowed k replacements can fix the mismatches
        # We can leave one odd unpaired, hence (odd_count // 2) replacements are needed
        if (odd_count // 2) <= k:
            result.append(True)
        else:
            result.append(False)
    return result

# Example usage:
s = "abcda"
queries = [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]]
print(canMakePaliQueries(s, queries))  # Output: [True, False, False, True, True]
← Back to All Questions