<p>You are given a string <code>s</code> and array <code>queries</code> where <code>queries[i] = [left<sub>i</sub>, right<sub>i</sub>, k<sub>i</sub>]</code>. We may rearrange the substring <code>s[left<sub>i</sub>...right<sub>i</sub>]</code> for each query and then choose up to <code>k<sub>i</sub></code> of them to replace with any lowercase English letter.</p>

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

<p>Return a boolean array <code>answer</code> where <code>answer[i]</code> is the result of the <code>i<sup>th</sup></code> query <code>queries[i]</code>.</p>

<p>Note that each letter is counted individually for replacement, so if, for example <code>s[left<sub>i</sub>...right<sub>i</sub>] = &quot;aaa&quot;</code>, and <code>k<sub>i</sub> = 2</code>, we can only replace two of the letters. Also, note that no query modifies the initial string <code>s</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example :</strong></p>

<pre>
<strong>Input:</strong> s = &quot;abcda&quot;, queries = [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]]
<strong>Output:</strong> [true,false,false,true,true]
<strong>Explanation:</strong>
queries[0]: substring = &quot;d&quot;, is palidrome.
queries[1]: substring = &quot;bc&quot;, is not palidrome.
queries[2]: substring = &quot;abcd&quot;, is not palidrome after replacing only 1 character.
queries[3]: substring = &quot;abcd&quot;, could be changed to &quot;abba&quot; which is palidrome. Also this can be changed to &quot;baab&quot; first rearrange it &quot;bacd&quot; then replace &quot;cd&quot; with &quot;ab&quot;.
queries[4]: substring = &quot;abcda&quot;, could be changed to &quot;abcba&quot; which is palidrome.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;lyb&quot;, queries = [[0,1,0],[2,2,1]]
<strong>Output:</strong> [false,true]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length, queries.length &lt;= 10<sup>5</sup></code></li>
	<li><code>0 &lt;= left<sub>i</sub> &lt;= right<sub>i</sub> &lt; s.length</code></li>
	<li><code>0 &lt;= k<sub>i</sub> &lt;= s.length</code></li>
	<li><code>s</code> consists of lowercase English letters.</li>
</ul>

// TC: O(m + n)
// SC:
//   Computation: O(n)
//   Output: O(m)
class Solution {
public:
  vector<bool> canMakePaliQueries(string s, vector<vector<int>>& queries) {
    int n = s.size();
    vector<bitset<26>> counts(1);

    for (auto const& c: s) {
      auto cur = counts.back();
      cur.flip(c - 'a');
      counts.push_back(std::move(cur));
    }

    vector<bool> out;
    for (auto const& query: queries) {
      int k = 2 * query[2] + 1;
      if ((counts[query[1] + 1] ^ counts[query[0]]).count() <= k) {
        out.push_back(true);
      } else {
        out.push_back(false);
      }
    }

    return out;
  }
};

#if 0
// TC: O(m + n)
// SC:
//   Computation: O(n)
//   Output: O(m)
class Solution {
public:
  vector<bool> canMakePaliQueries(string s, vector<vector<int>>& queries) {
    int n = s.size();
    vector<vector<int>> counts(n + 1, vector<int>(26));

    for (int i = 0; i < n; i++) {
      counts[i + 1] = counts[i];
      counts[i + 1][s[i] - 'a']++;
    }

    int m = queries.size();
    vector<bool> out(m, true);
    for (int i = 0; i < m; i++) {
      auto const& query = queries[i];
      int k = 2 * query[2] + 1;
      for (int j = 0; j < 26; j++) {
        int count = counts[query[1] + 1][j] - counts[query[0]][j];
        if (count % 2 > 0) {
          k--;
          if (k < 0) {
            out[i] = false;
            break;
          }
        }
      }
    }

    return out;
  }
};
#endif
100909