Palindrome Rearrangement Queries Solution in Java

Problem Description

Ah, the age-old question: can we rearrange a string into a palindrome? It’s like asking if you can fit a square peg into a round hole—sometimes it works, and sometimes you just end up with a mess. In the world of LeetCode, the problem of Palindrome Rearrangement Queries challenges you to determine if certain substrings of a given string can be rearranged to form a palindrome.

Imagine you have a string, say “aabb”, and you want to know if you can rearrange the substring from index 0 to 2 and the substring from index 2 to 3 into palindromes. Spoiler alert: you can! But what if you had “abc” instead? Well, good luck with that!

To make things even more interesting, you’ll be given multiple queries, and for each query, you need to check if the specified substrings can be rearranged into palindromes. It’s like a game of Tetris, but instead of fitting blocks, you’re fitting letters into a symmetrical shape.

Solution in Java


class Solution {
  public boolean[] canMakePalindromeQueries(String s, int[][] queries) {
    final int n = s.length();
    final int[] mirroredDiffs = getMirroredDiffs(s);
    final int[][] counts = getCounts(s);
    boolean[] ans = new boolean[queries.length];

    for (int i = 0; i < queries.length; i++) {
      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;
      final int rb = n - b;
      final int rc = n - c;
      final int rd = n - d;

      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 {
        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;
  }
}

Approach Explanation

The solution employs a clever approach using two main helper functions: getMirroredDiffs and getCounts. The getMirroredDiffs function calculates the number of differing characters between the first half of the string and its mirrored second half. Meanwhile, getCounts keeps track of character frequencies up to each index in the string.

For each query, the solution checks if the specified substrings can be rearranged into palindromes by comparing character counts and ensuring that the differences in characters fall within acceptable limits. It’s like a meticulous chef ensuring that all ingredients are perfectly balanced before baking a cake—no one wants a lopsided dessert!

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n + q * m)
Space Complexity	O(n)

Real-World Example

Imagine you’re at a party, and you want to arrange the guests in such a way that they can form pairs for a dance. If you have an odd number of guests, someone will be left out—just like how a string with an odd number of characters can’t form a palindrome. The solution helps you figure out if you can rearrange the guests (characters) to ensure everyone has a partner (can form a palindrome).