Skip to content

2983. Palindrome Rearrangement Queries

  • Time: $O(26n) = O(n)$
  • Space: $O(26n) = O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
class Solution {
 public:
  vector<bool> canMakePalindromeQueries(string s,
                                        vector<vector<int>>& queries) {
    const int n = s.length();
    // mirroredDiffs[i] := the number of different letters between the first i
    // letters of s[0..n / 2) and the first i letters of s[n / 2..n)[::-1]
    const vector<int> mirroredDiffs = getMirroredDiffs(s);
    // counts[i] := the count of s[0..i)
    const vector<vector<int>> counts = getCounts(s);
    vector<bool> ans;

    for (const vector<int>& query : queries) {
      // Use left-closed, right-open intervals to facilitate the calculation.
      //   ...... [a, b) ...|... [rb, ra) ......
      //   .... [rd, rc) .....|..... [c, d) ....
      const int a = query[0];
      const int b = query[1] + 1;
      const int c = query[2];
      const int d = query[3] + 1;
      const int ra = n - a;  // the reflected index of a in s[n / 2..n)
      const int rb = n - b;  // the reflected index of b in s[n / 2..n)
      const int rc = n - c;  // the reflected index of c in s[n / 2..n)
      const int rd = n - d;  // the reflected index of d in s[n / 2..n)
      // No difference is allowed outside the query ranges.
      if (min(a, rd) > 0 && mirroredDiffs[min(a, rd)] > 0 ||
          n / 2 > max(b, rc) &&
              mirroredDiffs[n / 2] - mirroredDiffs[max(b, rc)] > 0 ||
          rd > b && mirroredDiffs[rd] - mirroredDiffs[b] > 0 ||
          a > rc && mirroredDiffs[a] - mirroredDiffs[rc] > 0) {
        ans.push_back(false);
      } else {
        // The `count` map of the intersection of [a, b) and [rd, rc) in
        // s[0..n / 2) must equate to the `count` map of the intersection of
        // [c, d) and [rb, ra) in s[n / 2..n).
        vector<int> leftRangeCount = subtractArrays(counts[b], counts[a]);
        vector<int> rightRangeCount = subtractArrays(counts[d], counts[c]);
        if (a > rd)
          rightRangeCount = subtractArrays(
              rightRangeCount, subtractArrays(counts[min(a, rc)], counts[rd]));
        if (rc > b)
          rightRangeCount = subtractArrays(
              rightRangeCount, subtractArrays(counts[rc], counts[max(b, rd)]));
        if (c > rb)
          leftRangeCount = subtractArrays(
              leftRangeCount, subtractArrays(counts[min(c, ra)], counts[rb]));
        if (ra > d)
          leftRangeCount = subtractArrays(
              leftRangeCount, subtractArrays(counts[ra], counts[max(d, rb)]));
        ans.push_back(ranges::all_of(leftRangeCount, [](int freq) {
          return freq >= 0;
        }) && ranges::all_of(rightRangeCount, [](int freq) {
          return freq >= 0;
        }) && leftRangeCount == rightRangeCount);
      }
    }

    return ans;
  }

 private:
  vector<int> getMirroredDiffs(const string& s) {
    vector<int> diffs(1);
    for (int i = 0, j = s.length() - 1; i < j; ++i, --j)
      diffs.push_back(diffs.back() + (s[i] != s[j] ? 1 : 0));
    return diffs;
  }

  vector<vector<int>> getCounts(const string& s) {
    vector<int> count(26);
    vector<vector<int>> counts{count};
    for (const char c : s) {
      ++count[c - 'a'];
      counts.push_back(count);
    }
    return counts;
  }

  vector<int> subtractArrays(const vector<int>& a, const vector<int>& b) {
    vector<int> res;
    for (int i = 0; i < a.size(); ++i)
      res.push_back(a[i] - b[i]);
    return res;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
class Solution {
  public boolean[] canMakePalindromeQueries(String s, int[][] queries) {
    final int n = s.length();
    // mirroredDiffs[i] := the number of different letters between the first i
    // letters of s[0..n / 2) and the first i letters of s[n / 2..n)[::-1]
    final int[] mirroredDiffs = getMirroredDiffs(s);
    // counts[i] := the count of s[0..i)
    final int[][] counts = getCounts(s);
    boolean[] ans = new boolean[queries.length];

    for (int i = 0; i < queries.length; i++) {
      // Use left-closed, right-open intervals to facilitate the calculation.
      //   ...... [a, b) ...|... [rb, ra) ......
      //   .... [rd, rc) .....|..... [c, d) ....
      int[] query = queries[i];
      final int a = query[0];
      final int b = query[1] + 1;
      final int c = query[2];
      final int d = query[3] + 1;
      final int ra = n - a; // the reflected index of a in s[n / 2..n)
      final int rb = n - b; // the reflected index of b in s[n / 2..n)
      final int rc = n - c; // the reflected index of c in s[n / 2..n)
      final int rd = n - d; // the reflected index of d in s[n / 2..n)
      // No difference is allowed outside the query ranges.
      if ((Math.min(a, rd) > 0 && mirroredDiffs[Math.min(a, rd)] > 0) ||
          (n / 2 > Math.max(b, rc) && mirroredDiffs[n / 2] - mirroredDiffs[Math.max(b, rc)] > 0) ||
          (rd > b && mirroredDiffs[rd] - mirroredDiffs[b] > 0) ||
          (a > rc && mirroredDiffs[a] - mirroredDiffs[rc] > 0)) {
        ans[i] = false;
      } else {
        // The `count` map of the intersection of [a, b) and [rd, rc) in
        // s[0..n / 2) must equate to the `count` map of the intersection of
        // [c, d) and [rb, ra) in s[n / 2..n).
        int[] leftRangeCount = subtractArrays(counts[b], counts[a]);
        int[] rightRangeCount = subtractArrays(counts[d], counts[c]);
        if (a > rd)
          rightRangeCount =
              subtractArrays(rightRangeCount, subtractArrays(counts[Math.min(a, rc)], counts[rd]));
        if (rc > b)
          rightRangeCount =
              subtractArrays(rightRangeCount, subtractArrays(counts[rc], counts[Math.max(b, rd)]));
        if (c > rb)
          leftRangeCount =
              subtractArrays(leftRangeCount, subtractArrays(counts[Math.min(c, ra)], counts[rb]));
        if (ra > d)
          leftRangeCount =
              subtractArrays(leftRangeCount, subtractArrays(counts[ra], counts[Math.max(d, rb)]));
        ans[i] = Arrays.stream(leftRangeCount).allMatch(freq -> freq >= 0) &&
                 Arrays.stream(rightRangeCount).allMatch(freq -> freq >= 0) &&
                 Arrays.equals(leftRangeCount, rightRangeCount);
      }
    }

    return ans;
  }

  private int[] getMirroredDiffs(final String s) {
    int[] diffs = new int[s.length() / 2 + 1];
    for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
      diffs[i + 1] = diffs[i] + (s.charAt(i) != s.charAt(j) ? 1 : 0);
    }
    return diffs;
  }

  private int[][] getCounts(final String s) {
    int[][] counts = new int[s.length() + 1][26];
    int[] count = new int[26];
    for (int i = 0; i < s.length(); ++i) {
      ++count[s.charAt(i) - 'a'];
      System.arraycopy(count, 0, counts[i + 1], 0, 26);
    }
    return counts;
  }

  private int[] subtractArrays(int[] a, int[] b) {
    int[] res = new int[a.length];
    for (int i = 0; i < a.length; ++i)
      res[i] = a[i] - b[i];
    return res;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
class Solution:
  def canMakePalindromeQueries(
      self,
      s: str,
      queries: list[list[int]],
  ) -> list[bool]:
    n = len(s)
    # mirroredDiffs[i] := the number of different letters between the first i
    # letters of s[0..n / 2) and the first i letters of s[n / 2..n)[::-1]
    mirroredDiffs = self._getMirroredDiffs(s)
    # counts[i] := the count of s[0..i)
    counts = self._getCounts(s)
    ans = []

    def subtractArrays(a: list[int], b: list[int]):
      return [x - y for x, y in zip(a, b)]

    for a, b, c, d in queries:
      # Use left-closed, right-open intervals to facilitate the calculation.
      #   ...... [a, b) ...|... [rb, ra) ......
      #   .... [rd, rc) .....|..... [c, d) ....
      b += 1
      d += 1
      ra = n - a  # the reflected index of a in s[n / 2..n)
      rb = n - b  # the reflected index of b in s[n / 2..n)
      rc = n - c  # the reflected index of c in s[n / 2..n)
      rd = n - d  # the reflected index of d in s[n / 2..n)
      # No difference is allowed outside the query ranges.
      if ((min(a, rd) > 0 and mirroredDiffs[min(a, rd)] > 0) or
         (n // 2 > max(b, rc) and
          mirroredDiffs[n // 2] - mirroredDiffs[max(b, rc)] > 0) or
         (rd > b and mirroredDiffs[rd] - mirroredDiffs[b] > 0) or
         (a > rc and mirroredDiffs[a] - mirroredDiffs[rc] > 0)):
        ans.append(False)
      else:
        # The `count` map of the intersection of [a, b) and [rd, rc) in
        # s[0..n / 2) must equate to the `count` map of the intersection of
        # [c, d) and [rb, ra) in s[n / 2..n).
        leftRangeCount = subtractArrays(counts[b], counts[a])
        rightRangeCount = subtractArrays(counts[d], counts[c])
        if a > rd:
          rightRangeCount = subtractArrays(
              rightRangeCount, subtractArrays(counts[min(a, rc)], counts[rd]))
        if rc > b:
          rightRangeCount = subtractArrays(
              rightRangeCount, subtractArrays(counts[rc], counts[max(b, rd)]))
        if c > rb:
          leftRangeCount = subtractArrays(
              leftRangeCount, subtractArrays(counts[min(c, ra)], counts[rb]))
        if ra > d:
          leftRangeCount = subtractArrays(
              leftRangeCount, subtractArrays(counts[ra], counts[max(d, rb)]))
        ans.append(min(leftRangeCount) >= 0
                   and min(rightRangeCount) >= 0
                   and leftRangeCount == rightRangeCount)

    return ans

  def _getMirroredDiffs(self, s: str) -> list[int]:
    diffs = [0]
    for i, j in zip(range(len(s)), reversed(range(len(s)))):
      if i >= j:
        break
      diffs.append(diffs[-1] + (s[i] != s[j]))
    return diffs

  def _getCounts(self, s: str) -> list[list[int]]:
    count = [0] * 26
    counts = [count.copy()]
    for c in s:
      count[string.ascii_lowercase.index(c)] += 1
      counts.append(count.copy())
    return counts