<p>You are given two <strong>positive</strong> integers <code>n</code> and <code>k</code>.</p>

<p>An integer <code>x</code> is called <strong>k-palindromic</strong> if:</p>

<ul>
	<li><code>x</code> is a <span data-keyword="palindrome-integer">palindrome</span>.</li>
	<li><code>x</code> is divisible by <code>k</code>.</li>
</ul>

<p>Return the<strong> largest</strong> integer having <code>n</code> digits (as a string) that is <strong>k-palindromic</strong>.</p>

<p><strong>Note</strong> that the integer must <strong>not</strong> have leading zeros.</p>

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

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">n = 3, k = 5</span></p>

<p><strong>Output:</strong> <span class="example-io">&quot;595&quot;</span></p>

<p><strong>Explanation:</strong></p>

<p>595 is the largest k-palindromic integer with 3 digits.</p>
</div>

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

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">n = 1, k = 4</span></p>

<p><strong>Output:</strong> <span class="example-io">&quot;8&quot;</span></p>

<p><strong>Explanation:</strong></p>

<p>4 and 8 are the only k-palindromic integers with 1 digit.</p>
</div>

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

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">n = 5, k = 6</span></p>

<p><strong>Output:</strong> <span class="example-io">&quot;89898&quot;</span></p>
</div>

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

<ul>
	<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= k &lt;= 9</code></li>
</ul>

class Solution:
  def largestPalindrome(self, n: int, k: int) -> str:
    p = [1 % k] * n
    for i in range(n - 2, -1, -1):
      p[i] = p[i + 1] * 10 % k
    j = n
    for i in range(n // 2):
      j -= 1
      p[i] = (p[i] + p[j]) % k
    m = (n + 1) // 2
    a = [[-1] * (m + 1) for _ in range(k)]
    a[0][m] = 0
    for i in range(m - 1, -1, -1):
      for j in range(k):
        if a[j][i + 1] >= 0:
          for d in range(10):
            x = (j + d * p[i]) % k
            a[x][i] = max(a[x][i], d)
    b = []
    x = 0
    # print(*a, sep='\n')
    for i in range(m):
      b.append(a[x][i])
      x = (x - a[x][i] * p[i]) % k
    for i in range(m, n):
      b.append(b[n - 1 - i])
    return ''.join(map(str, b))
        
30018