# Super Palindromes
**Difficulty:** HARD
[External](https://leetcode.com/problems/super-palindromes)
Canonical: https://scaleengineer.com/dsa/problems/super-palindromes
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**Data structures:** String
---
## Problem
Let's say a positive integer is a **super-palindrome** if it is a palindrome, and it is also the square of a palindrome.

Given two positive integers `left` and `right` represented as strings, return _the number of **super-palindromes** integers in the inclusive range_ `[left, right]`.

**Example 1:**

**Input:** left = "4", right = "1000"
**Output:** 4
**Explanation**: 4, 9, 121, and 484 are superpalindromes.
Note that 676 is not a superpalindrome: 26 * 26 = 676, but 26 is not a palindrome.

**Example 2:**

**Input:** left = "1", right = "2"
**Output:** 1

**Constraints:**

* `1 <= left.length, right.length <= 18`
* `left` and `right` consist of only digits.
* `left` and `right` cannot have leading zeros.
* `left` and `right` represent integers in the range `[1, 1018 - 1]`.
* `left` is less than or equal to `right`.

# Approaches
## Brute Force Iteration Over the Range
This is the most straightforward but highly inefficient approach. The idea is to iterate through every integer `x` in the given range `[left, right]`. For each integer, we perform a series of checks to determine if it's a super-palindrome.
**Time:** `O((R - L) * log(R))`. The loop runs `R - L` times. Inside the loop, `sqrt` takes `O(log(R))` time, and palindrome checks also take `O(log(R))` time (proportional to the number of digits). Given `R` can be up to `10^18`, this is far too slow. · **Space:** `O(log(R))` to store the string representation of the numbers for palindrome checks.
**Pros:** Simple to understand and implement.
**Cons:** Extremely inefficient. The range `[left, right]` can be up to `[1, 10^18]`, making the loop infeasible. It will result in a "Time Limit Exceeded" error on any reasonably large test case.
### Explanation
First, we convert the input strings `left` and `right` to long integers, let's call them `L` and `R`. We then loop through each number `x` from `L` to `R`. Inside the loop, for each `x`, we check if it's a super-palindrome:
1.  **Check if `x` is a perfect square.** We calculate the integer square root of `x`, let's say `p = (long)sqrt(x)`. If `p * p` is not equal to `x`, then `x` is not a perfect square, and we move to the next number.
2.  **Check if `x` is a palindrome.** We convert `x` to a string and check if the string reads the same forwards and backward.
3.  **Check if the root `p` is a palindrome.** If the first two conditions are met, we then check if the square root `p` is also a palindrome.
If all three conditions are satisfied, we increment a counter. After checking all numbers in the range, the value of the counter is our answer. A helper function `isPalindrome(long n)` would be useful, which converts the number to a string and checks for the palindrome property.
```java
class Solution {
    public int superpalindromesInRange(String left, String right) {
        long L = Long.parseLong(left);
        long R = Long.parseLong(right);
        int count = 0;
        // This loop is too slow and will time out.
        for (long i = L; i <= R; i++) {
            if (isSuperPalindrome(i)) {
                count++;
            }
        }
        return count;
    }

    private boolean isSuperPalindrome(long n) {
        if (!isPalindrome(n)) {
            return false;
        }
        long sqrtN = (long) Math.sqrt(n);
        if (sqrtN * sqrtN != n) {
            return false;
        }
        return isPalindrome(sqrtN);
    }

    private boolean isPalindrome(long n) {
        String s = String.valueOf(n);
        int left = 0, right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left++) != s.charAt(right--)) {
                return false;
            }
        }
        return true;
    }
}
```
### Algorithm
*   Parse `left` and `right` strings to `long` integers `L` and `R`.
*   Initialize a counter `count` to 0.
*   Iterate through each integer `x` from `L` to `R`.
*   For each `x`, check if it's a super-palindrome:
    *   Calculate `p = sqrt(x)`.
    *   If `p * p == x` and `isPalindrome(x)` and `isPalindrome(p)`, increment `count`.
*   Return `count`.

## Improved Brute Force by Iterating Through Roots
A significant improvement over the first approach is to change the iteration space. Instead of checking every number `S` in the range `[L, R]`, we can generate potential super-palindromes by iterating through possible roots `P`. If `S` is in the range `[1, 10^18]`, its root `P` must be in the range `[1, 10^9]`.
**Time:** `O(sqrt(R) * log(R))`. The loop runs up to `10^9` times. The palindrome checks take `O(log(p))` and `O(log(p^2))`, which is `O(log(R))`. This is too slow. · **Space:** `O(log(R))` for palindrome checks.
**Pros:** Much more efficient than the first approach by reducing the search space from `[L, R]` to `[1, sqrt(R)]`.
**Cons:** Still too slow. The loop runs up to `10^9` times, which will cause a "Time Limit Exceeded" error.
### Explanation
The core idea is to iterate through all integers `p` from 1 up to `10^9` (the square root of the maximum possible value of `right`). For each integer `p`, we first check if it's a palindrome. If `p` is a palindrome, we calculate its square, `s = p * p`. We must handle potential overflows, although for `p <= 10^9`, `p*p` fits within a `long`. If `s` exceeds the upper bound `R`, we can stop iterating because subsequent squares will also be too large. If `s` is within the range `[L, R]`, we then check if `s` is also a palindrome. If both `p` and `s` are palindromes and `s` is in the required range, we increment our count. This approach drastically reduces the number of iterations from `R - L` (up to `10^18`) to `10^9`. However, `10^9` iterations are still too many for a typical time limit of a few seconds.
```java
class Solution {
    public int superpalindromesInRange(String left, String right) {
        long L = Long.parseLong(left);
        long R = Long.parseLong(right);
        int count = 0;
        long limit = 1000000000L; // sqrt(10^18) = 10^9

        // This loop is still too slow.
        for (long p = 1; p < limit; p++) {
            if (isPalindrome(p)) {
                long s = p * p;
                if (s > R) {
                    break;
                }
                if (s >= L && isPalindrome(s)) {
                    count++;
                }
            }
        }
        return count;
    }

    private boolean isPalindrome(long n) {
        String s = String.valueOf(n);
        int left = 0, right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left++) != s.charAt(right--)) {
                return false;
            }
        }
        return true;
    }
}
```
### Algorithm
*   Parse `left` and `right` strings to `long` integers `L` and `R`.
*   Initialize `count` to 0.
*   Calculate the upper limit for the root `p` as `sqrt(R)`.
*   Iterate `p` from `1` up to this limit.
*   Inside the loop:
    *   If `p` is a palindrome:
        *   Calculate `s = p * p`.
        *   If `s > R`, break the loop.
        *   If `s >= L` and `s` is also a palindrome, increment `count`.
*   Return `count`.

## Efficient Approach by Generating Palindromic Roots
The most efficient approach avoids checking non-palindromic numbers for the root `P`. Instead of iterating through all numbers up to `10^9` and checking if they are palindromes, we can directly generate only the palindromic numbers. The number of palindromes up to `10^9` is relatively small (around 200,000), making this approach feasible.
**Time:** `O(W * log(R))`, where `W` is the number of candidates for the first half of the root (`10^5` in this case). `log(R)` is the cost of palindrome checking (the number of digits in `R` is at most 18). The complexity is roughly `O(10^5 * 18)`, which is very fast. · **Space:** `O(log(R))` for storing string representations of numbers during palindrome generation and checking. This is effectively constant space as `log(R)` is small (at most 18).
**Pros:** Highly efficient and passes within the time limits.; The number of candidates for the root `P` is very small (`~2 * 10^5`), making the number of checks minimal.
**Cons:** The logic for generating palindromes is slightly more complex than the brute-force approaches.
### Explanation
A palindrome is constructed from its first half. For example, from `123`, we can construct the odd-length palindrome `12321` and the even-length palindrome `123321`. The root `P` of a super-palindrome `S <= 10^18` must be less than `10^9`. A number less than `10^9` has at most 9 digits. The first half of a 9-digit palindrome has 5 digits (e.g., `abcde` for `abcdedcba`). The largest possible first half is `99999`. Therefore, we only need to iterate through numbers `k` from `1` to `100,000` to form the first half of our palindromic roots. The algorithm proceeds as follows:
1.  Parse `left` and `right` to `long`s `L` and `R`.
2.  Iterate `k` from `1` to `100,000`.
3.  **Generate odd-length palindromes `P`**:
    *   From `k`, construct an odd-length palindrome `p`. For `k=123`, `p=12321`.
    *   Calculate `s = p * p`.
    *   If `s > R`, we can stop this loop as subsequent squares will be larger.
    *   If `s >= L` and `isPalindrome(s)`, increment the count.
4.  **Generate even-length palindromes `P`**:
    *   From `k`, construct an even-length palindrome `p`. For `k=123`, `p=123321`.
    *   Calculate `s = p * p`.
    *   If `s > R`, stop this loop.
    *   If `s >= L` and `isPalindrome(s)`, increment the count.
This method drastically cuts down the number of candidates for `P` that we need to check, leading to a very fast solution.
```java
class Solution {
    public int superpalindromesInRange(String left, String right) {
        long L = Long.parseLong(left);
        long R = Long.parseLong(right);
        int count = 0;
        int LIMIT = 100000;

        // Odd length palindromic roots
        for (int i = 1; i < LIMIT; i++) {
            String s = Integer.toString(i);
            StringBuilder reversedS = new StringBuilder(s).reverse();
            String palindromeStr = s + reversedS.substring(1);
            long p = Long.parseLong(palindromeStr);
            long pSquare = p * p;

            if (pSquare > R) {
                break;
            }
            if (pSquare >= L && isPalindrome(pSquare)) {
                count++;
            }
        }

        // Even length palindromic roots
        for (int i = 1; i < LIMIT; i++) {
            String s = Integer.toString(i);
            String reversedS = new StringBuilder(s).reverse().toString();
            String palindromeStr = s + reversedS;
            long p = Long.parseLong(palindromeStr);
            long pSquare = p * p;

            if (pSquare > R) {
                break;
            }
            if (pSquare >= L && isPalindrome(pSquare)) {
                count++;
            }
        }

        return count;
    }

    private boolean isPalindrome(long n) {
        String s = Long.toString(n);
        int left = 0;
        int right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left++) != s.charAt(right--)) {
                return false;
            }
        }
        return true;
    }
}
```
### Algorithm
*   Parse `left` and `right` strings to `long` integers `L` and `R`.
*   Initialize `count` to 0.
*   Define a limit for the first half of the root, `LIMIT = 100000`.
*   **Odd-length roots:** Loop `k` from `1` to `LIMIT`.
    *   Construct odd-length palindrome `p` from `k`.
    *   Calculate `s = p * p`.
    *   If `s > R`, break.
    *   If `s >= L` and `isPalindrome(s)`, increment `count`.
*   **Even-length roots:** Loop `k` from `1` to `LIMIT`.
    *   Construct even-length palindrome `p` from `k`.
    *   Calculate `s = p * p`.
    *   If `s > R`, break.
    *   If `s >= L` and `isPalindrome(s)`, increment `count`.
*   Return `count`.

# Solutions
### Java

```java
class Solution {
public
  int superpalindromesInRange(String L, String R) {
    long squareLow = Long.parseLong(L), squareHigh = Long.parseLong(R);
    long low = (long)Math.ceil(Math.sqrt(squareLow));
    long high = (long)Math.floor(Math.sqrt(squareHigh));
    int count = 0;
    for (int i = 1; i < 100000; i++) {
      long palindrome = getOddLengthPalindrome(i);
      if (palindrome < low)
        continue;
      else if (palindrome > high)
        break;
      else {
        long square = palindrome * palindrome;
        if (isPalindrome(square))
          count++;
      }
    }
    for (int i = 1; i < 100000; i++) {
      long palindrome = getEvenLengthPalindrome(i);
      if (palindrome < low)
        continue;
      else if (palindrome > high)
        break;
      else {
        long square = palindrome * palindrome;
        if (isPalindrome(square))
          count++;
      }
    }
    return count;
  }
public
  long getOddLengthPalindrome(int num) {
    StringBuffer sb = new StringBuffer(String.valueOf(num));
    int length = sb.length();
    for (int i = length - 2; i >= 0; i--)
      sb.append(sb.charAt(i));
    return Long.parseLong(sb.toString());
  }
public
  long getEvenLengthPalindrome(int num) {
    StringBuffer sb = new StringBuffer(String.valueOf(num));
    int length = sb.length();
    for (int i = length - 1; i >= 0; i--)
      sb.append(sb.charAt(i));
    return Long.parseLong(sb.toString());
  }
public
  boolean isPalindrome(long num) {
    char[] array = String.valueOf(num).toCharArray();
    int left = 0, right = array.length - 1;
    while (left < right) {
      if (array[left] != array[right])
        return false;
      left++;
      right--;
    }
    return true;
  }
}

```

### Python

```python
class Solution:
    def superpalindromesInRange(self, L, R): """ :type L: str :type R: str :rtype: int """ que = collections . deque(["11", "22"]) candi = set() while que: size = len(que) for _ in range(size): p = que . popleft() candi . add(p) if int(p) ** 2 > int(R): continue for j in ["0", "1", "2"]: q = (p[: len(p) // 2] + j + p[len(p) // 2:]) que . append(q) candi . add("1") candi . add("2") candi . add("3") res = 0 for cand in candi: if int(L) <= int(cand) ** 2 <= int(R) and self . isPalindromes(int(cand) ** 2): res += 1 return res def isPalindromes(self, s): s = str(s) N = len(s) for l in range(1, N // 2): if s[l] != s[N - 1 - l]: return False return True

```

### CPP

```cpp
// OJ: https://leetcode.com/problems/super-palindromes/ // Time: O(W^(1/4)*logW) // Space: O(logW) class Solution { long getPalindrome ( long half , bool odd ) { long ans = half ; if ( odd ) half /= 10 ; for (; half ; half /= 10 ) ans = ans * 10 + half % 10 ; return ans ; } bool isPalindrome ( long n ) { long tmp = n , r = 0 ; for (; tmp ; tmp /= 10 ) r = r * 10 + tmp % 10 ; return r == n ; } public: int superpalindromesInRange ( string left , string right ) { long L = stoll ( left ), R = stoll ( right ), ans = 0 ; for ( int len = 1 ; true ; ++ len ) { for ( long half = pow ( 10L , ( len - 1 ) / 2 ), end = half * 10 ; half < end ; ++ half ) { long pal = getPalindrome ( half , len % 2 ), sq = pal * pal ; if ( sq < L ) continue ; if ( sq > R ) return ans ; ans += isPalindrome ( sq ); } } return 0 ; } };
```