<p>Let&#39;s say a positive integer is a <strong>super-palindrome</strong> if it is a palindrome, and it is also the square of a palindrome.</p>

<p>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>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> left = &quot;4&quot;, right = &quot;1000&quot;
<strong>Output:</strong> 4
<strong>Explanation</strong>: 4, 9, 121, and 484 are superpalindromes.
Note that 676 is not a superpalindrome: 26 * 26 = 676, but 26 is not a palindrome.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> left = &quot;1&quot;, right = &quot;2&quot;
<strong>Output:</strong> 1
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= left.length, right.length &lt;= 18</code></li>
	<li><code>left</code> and <code>right</code> consist of only digits.</li>
	<li><code>left</code> and <code>right</code> cannot have leading zeros.</li>
	<li><code>left</code> and <code>right</code> represent integers in the range <code>[1, 10<sup>18</sup> - 1]</code>.</li>
	<li><code>left</code> is less than or equal to <code>right</code>.</li>
</ul>

// class Solution {
// public:
//     int superpalindromesInRange(string L, string R) {
//         int res = 0;
//         long left = stol(L), right = stol(R);
//         helper("", left, right, res);
//         for (char c = '0'; c <= '9'; ++c) {
//             helper(string(1, c), left, right, res);
//         }
//         return res;
//     }
//     void helper(string cur, long& left, long& right, int& res) {
//         if (cur.size() > 9) return;
//         if (!cur.empty() && cur[0] != '0') {
//             long num = stol(cur);
//             num *= num;
//             if (num > right) return;
//             if (num >= left && isPalindrome(to_string(num))) ++res;
//          }
//          for (char c = '0'; c <= '9'; ++c) {
//             helper(string(1, c) + cur + string(1, c), left, right, res);
//         }
//     }
//     bool isPalindrome(string str) {
//         int left = 0, right = (int)str.size() - 1;
//         while (left < right) {
//             if (str[left++] != str[right--]) return false;
//         }
//         return true;
//     }
// };
class Solution 
{
    public:
    int superpalindromesInRange(string left, string right) 
    {
        long unsigned int supers[] = {1, 4, 9, 121, 484, 10201, 12321, 14641, 40804, 44944, 1002001, 1234321, 4008004, 100020001, 102030201, 104060401, 121242121, 123454321, 125686521, 400080004, 404090404, 10000200001, 10221412201, 12102420121, 12345654321, 40000800004, 1000002000001, 1002003002001, 1004006004001, 1020304030201, 1022325232201, 1024348434201, 1210024200121, 1212225222121, 1214428244121, 1232346432321, 1234567654321, 4000008000004, 4004009004004, 100000020000001, 100220141022001, 102012040210201, 102234363432201, 121000242000121, 121242363242121, 123212464212321, 123456787654321, 400000080000004, 10000000200000001, 10002000300020001, 10004000600040001, 10020210401202001, 10022212521222001, 10024214841242001, 10201020402010201, 10203040504030201, 10205060806050201, 10221432623412201, 10223454745432201, 12100002420000121, 12102202520220121, 12104402820440121, 12122232623222121, 12124434743442121, 12321024642012321, 12323244744232321, 12343456865434321, 12345678987654321, 40000000800000004, 40004000900040004};
        
        long unsigned int lower = stoi(left);
        long unsigned int upper = stoi(right);
        
        int l = 0;
        int r = 69;
        
        while(supers[l] < lower) l++;
        while(supers[r] > upper) r--;
        
        return r - l + 1;
    }

private:
    long unsigned int stoi(string& num)
    {
        long unsigned int ret = 0;
        for(char c:num)
        {
            ret *= 10;
            ret += c - '0';
        }
        
        return ret;
    }
};
7600