Count of palindromic strings of size upto N consisting of first K alphabets occurring at most twice | Function of return the number of palindromic strings of length N with first K alphabets possible ; If N is odd , half + 1 position can be filled to cope with the extra middle element ; K is reduced by one , because count of choices for the next position is reduced by 1 as a element can only once ; Return the possible count ; Function to find the count of palindromic string of first K characters according to the given criteria ; If N = 1 , then only K palindromic strings possible . ; If N = 2 , the 2 * K palindromic strings possible , K for N = 1 and K for N = 2 ; Initialize ans with the count of strings possible till N = 2 ; Return the possible count ; Driver Code
def lengthNPalindrome ( N , K ) : NEW_LINE INDENT half = N // 2 ; NEW_LINE if ( N & 1 ) : NEW_LINE INDENT half += 1 ; NEW_LINE DEDENT ans = 1 ; NEW_LINE for i in range ( 1 , half + 1 ) : NEW_LINE INDENT ans *= K ; NEW_LINE K -= 1 ; NEW_LINE DEDENT return ans ; NEW_LINE DEDENT def palindromicStrings ( N , K ) : NEW_LINE INDENT if ( N == 1 ) : NEW_LINE INDENT return K ; NEW_LINE DEDENT if ( N == 2 ) : NEW_LINE INDENT return 2 * K ; NEW_LINE DEDENT ans = 0 ; NEW_LINE ans += ( 2 * K ) ; NEW_LINE for i in range ( 3 , N + 1 ) : NEW_LINE INDENT ans += lengthNPalindrome ( i , K ) ; NEW_LINE DEDENT return ans ; NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT N = 4 ; K = 3 ; NEW_LINE print ( palindromicStrings ( N , K ) ) ; NEW_LINE DEDENT