Leetcode Problem 1177. Can Make Palindrome from Substring

1177. Can Make Palindrome from Substring

Leetcode Solutions

Prefix Sum and Bit Manipulation

  1. Initialize an array dp of length len(s) + 1 with all elements set to 0.
  2. Iterate over the string s, updating the dp array at each index i + 1 with the XOR of dp[i] and 1 << (ord(s[i]) - ord('a')).
  3. For each query [left, right, k], calculate the XOR of dp[right + 1] and dp[left] to get the parity difference.
  4. Count the number of set bits in the parity difference, which represents the number of characters with odd counts in the substring.
  5. If the number of set bits divided by 2 is less than or equal to k, the substring can be rearranged into a palindrome, so add True to the result list. Otherwise, add False.
  6. Return the result list.
UML Thumbnail

Character Frequency Count and Palindrome Check

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...