Code Implementation

class Solution:
    def superpalindromesInRange(self, left: str, right: str) -> int:
        def is_palindrome(x: str) -> bool:
            return x == x[::-1]
        
        L, R = int(left), int(right)
        MAGIC = 100000
        ans = 0

        # Odd length palindromes
        for k in range(MAGIC):
            s = str(k)
            t = s + s[-2::-1]  # create odd-length palindrome
            v = int(t) ** 2
            if v > R:
                break
            if v >= L and is_palindrome(str(v)):
                ans += 1

        # Even length palindromes
        for k in range(MAGIC):
            s = str(k)
            t = s + s[::-1]  # create even-length palindrome
            v = int(t) ** 2
            if v > R:
                break
            if v >= L and is_palindrome(str(v)):
                ans += 1

        return ans
    

class Solution {
public:
    bool isPalindrome(string s) {
        int i = 0, j = s.size() - 1;
        while (i < j) {
            if (s[i++] != s[j--]) return false;
        }
        return true;
    }
    int superpalindromesInRange(string left, string right) {
        long L = stol(left), R = stol(right);
        int MAGIC = 100000, ans = 0;

        // Odd length palindromes
        for (int k = 0; k < MAGIC; ++k) {
            string s = to_string(k);
            string t = s + string(s.rbegin() + 1, s.rend());
            long v = stol(t);
            v *= v;
            if (v > R) break;
            if (v >= L && isPalindrome(to_string(v))) ++ans;
        }

        // Even length palindromes
        for (int k = 0; k < MAGIC; ++k) {
            string s = to_string(k);
            string t = s + string(s.rbegin(), s.rend());
            long v = stol(t);
            v *= v;
            if (v > R) break;
            if (v >= L && isPalindrome(to_string(v))) ++ans;
        }

        return ans;
    }
};
    

class Solution {
    private boolean isPalindrome(String s) {
        int i = 0, j = s.length() - 1;
        while (i < j) {
            if (s.charAt(i++) != s.charAt(j--)) return false;
        }
        return true;
    }
    public int superpalindromesInRange(String left, String right) {
        long L = Long.parseLong(left), R = Long.parseLong(right);
        int MAGIC = 100000, ans = 0;
        
        // Odd length palindromes
        for (int k = 0; k < MAGIC; ++k) {
            String s = Integer.toString(k);
            StringBuilder sb = new StringBuilder(s);
            sb.append(new StringBuilder(s).reverse().substring(1));
            long v = Long.parseLong(sb.toString());
            v *= v;
            if (v > R) break;
            if (v >= L && isPalindrome(Long.toString(v))) ++ans;
        }

        // Even length palindromes
        for (int k = 0; k < MAGIC; ++k) {
            String s = Integer.toString(k);
            StringBuilder sb = new StringBuilder(s);
            sb.append(new StringBuilder(s).reverse());
            long v = Long.parseLong(sb.toString());
            v *= v;
            if (v > R) break;
            if (v >= L && isPalindrome(Long.toString(v))) ++ans;
        }
        return ans;
    }
}
    

var superpalindromesInRange = function(left, right) {
    function isPalindrome(s) {
        let i = 0, j = s.length - 1;
        while (i < j) {
            if (s[i++] !== s[j--]) return false;
        }
        return true;
    }
    const L = BigInt(left), R = BigInt(right);
    const MAGIC = 100000;
    let ans = 0;

    // Odd length palindromes
    for (let k = 0; k < MAGIC; ++k) {
        let s = k.toString();
        let t = s + s.slice(0, s.length - 1).split('').reverse().join('');
        let v = BigInt(t);
        v = v * v;
        if (v > R) break;
        if (v >= L && isPalindrome(v.toString())) ++ans;
    }

    // Even length palindromes
    for (let k = 0; k < MAGIC; ++k) {
        let s = k.toString();
        let t = s + s.split('').reverse().join('');
        let v = BigInt(t);
        v = v * v;
        if (v > R) break;
        if (v >= L && isPalindrome(v.toString())) ++ans;
    }

    return ans;
};
    

Problem Description

Given two positive integers represented as strings, left and right, return the number of super-palindromes within the inclusive range [left, right].

A super-palindrome is a number that is a palindrome and whose square root is also a palindrome (all in base 10). Both the number itself and its square root must not have leading zeros.

• The input numbers left and right can be very large (up to 10¹⁸), so they are given as strings.
• Each super-palindrome must be within the inclusive range [left, right].
• All numbers must be considered as positive integers without leading zeros.

Thought Process

At first glance, the problem seems to require checking every number between left and right to see if it is a palindrome and if its square root is also a palindrome. However, this brute-force approach is not feasible because the range can be enormous (up to 10¹⁸).

Instead, let's reverse the process: rather than checking every number in the range, we can check every palindrome whose square is within the range. Since the square root of a super-palindrome must also be a palindrome, we can generate palindromic numbers, square them, and check if the result is also a palindrome and falls within the given range.

This approach drastically reduces the number of candidates we need to check. The key insight is that there are far fewer palindromic numbers up to 10⁹ than there are numbers up to 10¹⁸.

Solution Approach

• Step 1: Generate Palindromic Roots
  • We generate all palindromic numbers (as possible square roots) up to 10⁹ (since (10⁹)² = 10¹⁸).
  • We do this by constructing palindromic numbers of both odd and even lengths.
• Step 2: Square and Check
  • For each palindromic root, compute its square.
  • Check if the square is within the range [left, right].
  • Check if the square itself is a palindrome.
• Step 3: Count Valid Super-Palindromes
  • If both conditions are met, increment the count.
• Why Generate Palindromic Roots?
  • Because only numbers whose square roots are palindromic can possibly be super-palindromes.
  • This avoids checking all numbers in the huge range.
• Why Both Odd and Even Lengths?
  • Palindromic numbers can have odd or even lengths, so we need to generate both types to cover all possible roots.

Example Walkthrough

Let's use left = "4" and right = "1000" as an example.

1. Generate palindromic roots:
   • Possible palindromic numbers in this range: 2, 3, 11, 22, 101, etc.
2. Check their squares:
   • 2² = 4 (palindrome, in range)
   • 3² = 9 (palindrome, in range)
   • 11² = 121 (palindrome, in range)
   • 22² = 484 (palindrome, in range)
   • 101² = 10201 (out of range)
3. Count valid super-palindromes:
   • 4, 9, 121, and 484 are all super-palindromes.
4. Final answer:
   • The function returns 4.

Time and Space Complexity

• Brute-force approach:
  • Time: O(N), where N is up to 10¹⁸ (not feasible).
  • Space: O(1), only a few variables.
• Optimized approach (palindromic roots):
  • Time: O(K * log K), where K is the number of palindromic roots we generate (up to about 10⁵).
  • For each root, we check if its square is a palindrome, which takes O(log N) time for string reversal.
  • Space: O(1), only a few variables used at a time.
• Why is it efficient?
  • Because the number of palindromic roots up to 10⁹ is small compared to the total range.

Summary

The main insight for solving the Super Palindromes problem is to generate all possible palindromic numbers as roots, square them, and check if both the root and the square are palindromes within the specified range. This avoids the infeasible brute-force approach and leverages the mathematical structure of palindromes to efficiently solve the problem. The solution is elegant because it reduces the search space from trillions of numbers to just a few hundred thousand candidates, making it practical and fast.