<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>

def is_ok(idx, res, n, k, idx_to_res, memo):
    if (idx, res) in memo:
        return memo[(idx, res)]
    
    if n % 2 == 1 and idx == n // 2:
        for v in range(9, -1, -1):
            if (idx_to_res[idx] * v) % k == res:
                memo[(idx, res)] = v
                return v
        memo[(idx, res)] = None
        return None
    elif n % 2 == 0 and idx == (n - 1) // 2:
        for v in range(9, -1, -1):
            if (idx_to_res[idx] * v + idx_to_res[idx + 1] * v) % k == res:
                memo[(idx, res)] = v
                return v
        memo[(idx, res)] = None
        return None
    

    # (val * 2 + x ) % k == res 
    for v in range(9, -1, -1):
        need = (res + k - (idx_to_res[idx] * v + idx_to_res[n - 1 - idx] * v) % k) % k 

        tmp = is_ok(idx + 1, need, n, k, idx_to_res, memo) 
        if tmp is not None:
            memo[(idx, res)] = v
            return v
    
    memo[(idx, res)] = None
    return None


class Solution:
    def largestPalindrome(self, n: int, k: int) -> str:
        idx_to_res = [0] * n
        tmp = 1
        for idx in range(n - 1, -1, -1):
            idx_to_res[idx] = tmp
            tmp = (tmp * 10) %k

        memo = {}
        tmp = is_ok(0, 0, n, k, idx_to_res, memo)
        if memo[(0, 0)] is None:
            return 0
        
        # print(memo)

        res = []
        need = 0 
        for idx in range((n + 1) // 2):
            cur = memo[(idx, need)]
            res.append(cur)
            need = (need + k - (idx_to_res[idx] * cur + idx_to_res[n - 1 - idx] * cur ) % k) % k 

        if n % 2 == 0:
            i = 0
            while i < len(res):
                if res[i] == 0:
                    i += 1
                else:
                    break
            if i == len(res):
                return 0
            res = res[i:]
            res.extend(res[::-1])
            return ''.join([str(c) for c in res])
        else:
            i = 0
            while i < len(res):
                if res[i] == 0:
                    i += 1
                else:
                    break
            if i == len(res):
                return 0
            res = res[i:]
            res.extend(res[-2::-1])
            return ''.join([str(c) for c in res])
        
        # res = int(''.join([str(v) for v in res]))
        # while res and res % 10  == 0:
        #     res //= 10
        
        
        # if n % 2 == 0:
        #     i = 0
        #     while i < len(res):
        #         if res[i] == 0:
        #             i += 1
        #         else:
        #             break
        #     if i == len(res):
        #         return 0
        #     res = res[i : ]
        #     res.extend(res[::-1])
        # else:
        #     mid = res.pop(-1)
        #     while i < len(res):
        #         if res[i] == 0:
        #             i += 1
        #         else:
        #             break
        #     if i == len(res):
        #         return mid
        #     res.append(mid)
        #     res.extend(res[-2::-1])

        # return ''.join([str(v) for v in res])
        
93948