<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:
        """
        try DP
        though i think both solutions >=2200

        0 1 2 3     4->2
        0 1 2 3 4   5->3

        s[i]-> 10^(N-i-1)
        s[N-1-i]-> 10^(i)

        O(10nk)
        """
        INF=10**20
        halfN=-(-N//2)
        pow10=[None for _ in range(N)]
        pow10[0]=1
        for i in range(1,N):
            pow10[i]=pow10[i-1]*10
            pow10[i]%=k
        #print(pow10)
        """
        return True if [i:N-i] given aggRem(remainder) is possible
        """
        choices=[[None for _ in range(k)] for _ in range(N)]#store digit choisen
        @cache
        def dfs(i,aggRem):   
            if i==halfN:
                if aggRem==0:
                    return True
                return False
            
            #iterate choices for s[i] and s[N-1-i]
            for v in range(9,-1,-1):#greedy: from largest, break when found
                cur=aggRem
                cur+=v*pow10[N-i-1]
                if i!=N-1-i:
                    cur+=v*pow10[i]
                cur%=k
                if dfs(i+1,cur):
                    choices[i][aggRem]=choices[N-i-1][aggRem]=v
                    return True
            
            return False

        dfs(0,0)
        # for row in choices:
        #     print(row)
        ans=[None for _ in range(N)]
        aggRem=0
        for i in range(halfN):  #reconstruct ans
            v=choices[i][aggRem]
            # print(i,aggRem,v)
            ans[i]=str(v)
            aggRem+=v*pow10[N-i-1]
            if i!=N-1-i:
                ans[N-1-i]=str(v)
                aggRem+=v*pow10[i]
            aggRem%=k
        # print(ans)
        return ''.join(ans)



        



152551