> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Super Palindromes Python Solution with Tests

> Tested Python solution for LeetCode 906 with 33 pytest cases. Generate a practice environment with lcpy.

LeetCode 906, [Hard](/catalog/hard). Topics: [Math](/catalog/topics/math), [String](/catalog/topics/string), [Enumeration](/catalog/topics/enumeration). [View on LeetCode](https://leetcode.com/problems/super-palindromes/description/).

Generate this problem as a practice environment: tested reference solution, 33 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 906   # by problem number
lcpy gen -s super_palindromes   # by problem name
```

## 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 \<code>left\</code> and \<code>right\</code> represented as strings, return \<em>the number of \<strong>super-palindromes\</strong> integers in the inclusive range\</em> \<code>\[left, right]\</code>.

### Examples

```
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.
```

```
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, 10\<sup>18\</sup> - 1].
* left is less than or equal to right.

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/super_palindromes/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/super_palindromes/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Time: O(R^0.5 * log R) where R = int(right), over ~2 * 10^(d/2) palindrome roots
    # Space: O(1)
    def super_palindromes_in_range(self, left: str, right: str) -> int:
        lo, hi = int(left), int(right)
        count = 0
        # Palindromic roots with up to 9 digits: their squares cover up to 10^18 - 1.
        # Roots are visited in increasing order, so we can stop once we pass hi.
        for length in range(1, 10):
            half_len = (length + 1) // 2
            for half in range(10 ** (half_len - 1), 10**half_len):
                digits = str(half)
                if length % 2 == 0:
                    root = int(digits + digits[::-1])
                else:
                    root = int(digits + digits[-2::-1])
                square = root * root
                if square > hi:
                    return count
                if square >= lo and str(square) == str(square)[::-1]:
                    count += 1
        return count
```

## Complexity

| Time | Space |
| - | - |
| O(R^0.5 \* log R) where R = int(right), over \~2 \* 10^(d/2) palindrome roots | O(1) |

## Tags


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.