Medium

Can Make Palindrome from Substring

LAB

For each query [left,right,k], return true if the substring can be rearranged and changed in at most k positions to form a palindrome.

EXAMPLES

Example 1

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
]

FUNCTION SHAPE

s: stringqueries: intMatrix→boolArray

SOLUTION NOTE

Few things:
1. Rearrangement means order doesn't matter. So this means only the frequency count matters.
2. You can add and subtract counters... this is really useful.
3. Use the key property mentioned at the beginning, where palindromes can have at most 1 odd frequency character. So when we have more than 1 odd frequency character, we are forced to use some of our k operations to replace them.

Example: say there are 2 odd frequencies (a->3, b->9). Easy, just change 1. (change one a to b, OR change 1 b to an a)

Say there are 3 odd frequencies (a->3, b->9, c->5). This still takes just 1. (ex. change one a to b. KEEP THE c as is, just use it as the middle)

So it's basically just num_odd_freq // 2 is the number of moves required!

Open on LeetCode ↗