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].
• left is less than or equal to right.

class Solution {
    public int superpalindromesInRange(String left, String right) {
        Long l = Long.parseLong(left);
        Long r = Long.parseLong(right);
        int res = 0;
        for(long i = (long)Math.sqrt(l); i * i <= r; ) {
            long p = help(i);
            if(p * p <= r && ispal(p * p)) {
                res++;
            }
            i = p + 1;
        }    
        return res;
    }
    
    public long help(long l) {
        String s = l + "";
        int n = s.length();
        String half = s.substring(0, (n +1) / 2);
        String revhalf = new StringBuilder(half.substring(0, n / 2)).reverse().toString();
        long fir = Long.parseLong(half + revhalf);
        if(fir >= l) return fir;
        String sechalf = Long.toString(Long.valueOf(half) + 1);
        String revsec = new StringBuilder(sechalf.substring(0, n / 2)).reverse().toString();
        long sec = Long.valueOf(sechalf + revsec);
        return sec;
    }
    
    public boolean ispal(long l) {
        String s = "" + l;
        int le = 0, ri = s.length() - 1;
        while(le < ri) {
            if(s.charAt(le++) != s.charAt(ri--)) return false;
        }
        return true;
    }
}

https://leetcode.com/problems/super-palindromes/discuss/170774/Java-building-the-next-palindrome

从sqrt left开始找，每次都找下一个pal。help是如何找下一个pal，half是前半部分（可能是123of12345，或12of1234这种）。如果fir大于等于l，可以直接返回fir了，如果没有，比如1234的1221，这时下一个pal就应该是1331，得到的方法就是给上一个half + 1。然后再build一个pal返回。