1
class Solution {
2
  public int superpalindromesInRange(String left, String right) {
3
    int ans = 9 >= Long.parseLong(left) && 9 <= Long.parseLong(right) ? 1 : 0;
4

5
    for (int dig = 1; dig < 10; dig++) {
6
      boolean isOdd = dig % 2 > 0 && dig != 1;
7
      int innerLen = (dig >> 1) - 1,
8
          innerLim = Math.max(1, (int) Math.pow(2, innerLen)),
9
          midPos = dig >> 1,
10
          midLim = isOdd ? 3 : 1;
11
      for (int edge = 1; edge < 3; edge++) {
12
        char[] pal = new char[dig];
13
        Arrays.fill(pal, '0');
14
        pal[0] = (char) (edge + 48);
15
        pal[dig - 1] = (char) (edge + 48);
16
        if (edge == 2) {
17
          innerLim = 1;
18
          midLim = Math.min(midLim, 2);
19
        }
20
        for (int inner = 0; inner < innerLim; inner++) {
21
          if (inner > 0) {
22
            String innerStr = Integer.toString(inner, 2);
23
            while (innerStr.length() < innerLen) innerStr = "0" + innerStr;
24
            for (int i = 0; i < innerLen; i++) {
25
              pal[1 + i] = innerStr.charAt(i);
26
              pal[dig - 2 - i] = innerStr.charAt(i);
27
            }
28
          }
29
          for (int mid = 0; mid < midLim; mid++) {
30
            if (isOdd) pal[midPos] = (char) (mid + 48);
31
            String palin = new String(pal);
32
            long square = Long.parseLong(palin) * Long.parseLong(palin);
33
            if (square > Long.parseLong(right)) return ans;
34
            if (square >= Long.parseLong(left) && isPal(Long.toString(square))) ans++;
35
          }
36
        }
37
      }
38
    }
39
    return ans;
40
  }
41

42
  private boolean isPal(String str) {
43
    for (int i = 0, j = str.length() - 1; i < j; i++, j--)
44
      if (str.charAt(i) != str.charAt(j)) return false;
45
    return true;
46
  }
47
}