# LeetCode 906: Super Palindromes

## Problem Restatement

A positive integer is called a super-palindrome if:

1. The number itself is a palindrome.
2. It is the square of another palindrome.

We are given two positive integers `left` and `right` as strings.

Return how many super-palindromes are in the inclusive range:

```python
[left, right]
```

For example, `9` is a super-palindrome because:

```python
9 = 3 * 3
```

and both `9` and `3` are palindromes.

The official problem uses string inputs because the range can go up to around `10^18`. The definition and examples match the LeetCode statement.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Strings `left` and `right` |
| Output | Number of super-palindromes in the inclusive range |
| Rule 1 | The number must be a palindrome |
| Rule 2 | Its square root must also be a palindrome integer |
| Range | `left <= x <= right` |

Function shape:

```python
def superpalindromesInRange(left: str, right: str) -> int:
    ...
```

## Examples

Example 1:

```python
left = "4"
right = "1000"
```

The super-palindromes are:

```python
4, 9, 121, 484
```

They come from palindromic roots:

```python
2 * 2 = 4
3 * 3 = 9
11 * 11 = 121
22 * 22 = 484
```

Answer:

```python
4
```

`676` is a palindrome, but it is not counted because:

```python
676 = 26 * 26
```

and `26` is not a palindrome.

Example 2:

```python
left = "1"
right = "2"
```

The only valid number is:

```python
1
```

Answer:

```python
1
```

## First Thought: Check Every Number

A direct approach is to loop through every number from `left` to `right`.

For each number `x`:

1. Check whether `x` is a palindrome.
2. Check whether `x` has an integer square root.
3. Check whether that square root is also a palindrome.

This is far too slow because `right` can be as large as `10^18 - 1` under the constraints listed by common references for the problem.

We need to search through possible roots instead.

## Key Insight

If `x` is a super-palindrome, then:

```python
x = p * p
```

where `p` is a palindrome.

So instead of checking every possible `x`, we generate palindromic roots `p`, square them, and check whether the square is also a palindrome.

Since:

```python
x <= 10^18 - 1
```

we only need:

```python
p <= sqrt(10^18 - 1)
```

That is less than:

```python
10^9
```

But we still should not loop over all numbers up to `10^9`.

Instead, we generate only palindromic roots.

A palindrome root can be generated from its first half.

For example, from `"123"`:

Odd length palindrome:

```python
"123" + "21" = "12321"
```

Even length palindrome:

```python
"123" + "321" = "123321"
```

This gives all palindromic roots without testing every integer.

## Algorithm

Convert bounds to integers:

```python
L = int(left)
R = int(right)
```

Then enumerate possible first halves.

For each integer `half`:

1. Convert `half` to string.
2. Build an odd-length palindrome root.
3. Square it.
4. If the square is in range and is a palindrome, count it.
5. Build an even-length palindrome root.
6. Square it.
7. If the square is in range and is a palindrome, count it.

We can stop once the smallest generated square is larger than `R`, but using a safe fixed bound also works.

Since roots are below `10^9`, their first half has at most `5` digits. So enumerating `half` from `1` to `100000` is enough.

## Palindrome Check

We can check palindromes by converting the number to a string:

```python
def is_palindrome(x: int) -> bool:
    s = str(x)
    return s == s[::-1]
```

This is simple and fast enough here.

## Correctness

Every number counted by the algorithm is valid.

The algorithm only counts a square `square = root * root` when:

1. `root` was generated as a palindrome.
2. `square` lies in `[L, R]`.
3. `square` is also a palindrome.

Therefore, every counted number is a super-palindrome in the required range.

Now we show that every valid super-palindrome is counted.

Let `x` be any super-palindrome in `[L, R]`.

By definition, there exists a palindromic integer `p` such that:

```python
x = p * p
```

Since `x <= R <= 10^18 - 1`, we have `p < 10^9`.

Every positive palindrome less than `10^9` can be formed by taking its first half and mirroring it, either as an odd-length or even-length palindrome.

The algorithm enumerates all such first halves and constructs both odd and even palindromic roots.

So it eventually constructs `p`, computes `p * p`, checks that it lies in range, and counts it.

Thus no valid super-palindrome is missed.

## Complexity

| Metric | Value | Why |
|---|---:|---|
| Time | `O(100000 * d)` | We generate palindromic roots from up to `100000` halves and do digit checks |
| Space | `O(1)` | We only store counters and temporary strings |

Here `d` is the number of digits, at most `18` for the squared value.

## Implementation

```python
class Solution:
    def superpalindromesInRange(self, left: str, right: str) -> int:
        L = int(left)
        R = int(right)

        def is_palindrome(x: int) -> bool:
            s = str(x)
            return s == s[::-1]

        answer = 0

        for half in range(1, 100000):
            s = str(half)

            odd_root = int(s + s[-2::-1])
            odd_square = odd_root * odd_root

            if odd_square > R:
                break

            if odd_square >= L and is_palindrome(odd_square):
                answer += 1

            even_root = int(s + s[::-1])
            even_square = even_root * even_root

            if even_square >= L and even_square <= R and is_palindrome(even_square):
                answer += 1

        return answer
```

## Code Explanation

The bounds arrive as strings, so we convert them first:

```python
L = int(left)
R = int(right)
```

The helper checks whether a number reads the same backward and forward:

```python
def is_palindrome(x: int) -> bool:
    s = str(x)
    return s == s[::-1]
```

We enumerate possible left halves:

```python
for half in range(1, 100000):
```

For odd-length roots, we do not duplicate the middle digit:

```python
odd_root = int(s + s[-2::-1])
```

For example:

```python
s = "123"
odd_root = 12321
```

Then we square the root:

```python
odd_square = odd_root * odd_root
```

If the odd square already exceeds the right bound, later odd roots will only be larger, so we can stop:

```python
if odd_square > R:
    break
```

Then we count it if it is inside the range and palindromic:

```python
if odd_square >= L and is_palindrome(odd_square):
    answer += 1
```

For even-length roots, we mirror the whole half:

```python
even_root = int(s + s[::-1])
```

For example:

```python
s = "123"
even_root = 123321
```

Then we check its square in the same way:

```python
if even_square >= L and even_square <= R and is_palindrome(even_square):
    answer += 1
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.superpalindromesInRange("4", "1000") == 4
    assert s.superpalindromesInRange("1", "2") == 1
    assert s.superpalindromesInRange("1", "1") == 1
    assert s.superpalindromesInRange("2", "3") == 0
    assert s.superpalindromesInRange("9", "9") == 1
    assert s.superpalindromesInRange("121", "121") == 1
    assert s.superpalindromesInRange("122", "483") == 0
    assert s.superpalindromesInRange("484", "484") == 1

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `"4"` to `"1000"` | Main sample range |
| `"1"` to `"2"` | Small range with one valid value |
| `"1"` to `"1"` | Single-value inclusive bound |
| `"2"` to `"3"` | No valid super-palindrome |
| `"9"` to `"9"` | Single-value square of palindromic root |
| `"121"` to `"121"` | `11 * 11` |
| `"122"` to `"483"` | Gap between known values |
| `"484"` to `"484"` | `22 * 22` |