# Hackerrank Solution: Anti-Palindromic Strings

Original Problem

You are given two integers, $$N$$ and $$M$$. Count the number of strings of length $$N$$ (under the alphabet set of size $$M$$) that doesn't contain any palindromic string of the length greater than $$1$$ as a consecutive substring.

## Input Format

Several test cases will be given to you in a single file. The first line of the input will contain a single integer, $$T$$, the number of test cases.

Then there will be $$T$$ lines, each containing two space-separated integers, $$N$$ and $$M$$, denoting a single test case. The meanings of $$N$$ and $$M$$ are described in the Problem Statement above.

## Output Format

For each test case, output a single integer - the answer to the corresponding test case. This number can be huge, so output it modulo $$10^9+7$$

## Constraints

• $$1\leq T\leq 10^5$$
• $$1\leq N,M\leq 10^9$$

## Sample Input

2
2 2
2 3

## Sample Output

2
6

## Solution

Lets analyse the problem inductive.

### Case $$N=1$$:

Since no palindromes of length $$>1$$ are allowed, all possible characters can be used, resulting in $$M$$ combinations:

$\Gamma(M, N):= M$

### Case $$N=2$$:

Since palindromes can be formed only as $$AA$$, $$BB$$, $$CC$$ and so on, the second character must be different from the first, which reduces the number of possible characters for the second place by one:

$\Gamma(M, N):= M\cdot(M - 1)$

### Case $$N=3$$:

Since we can choose any character for the third place except the two before, the number of possibilities is reduced by one again:

$\Gamma(M, N):= M\cdot(M - 1)\cdot(M - 2)$

Lets take the example with $$M=3$$: AAA, AAB, AAC, ABA, ABB, ACA, ACC, BAA, BAB, BBA, BBB, BBC, BBB, BCB, CAA, CAC, CBB, CBC, CCA, CCB and CCC have all a palindromic pattern, while ABC, ACB, BAC, BCA, CAB and CBA are anipaledrome. Which demonstrates the reasoning behind the derived formula.

### Case $$N>3$$:

Since we are looking for strings that do not contain any palindromic consecutive substrings, it is sufficient to exclude two and three-digit palindromes, since all longer palindromes contain them anyway. That is

$\Gamma(M, N):= M\cdot(M - 1)\cdot(M - 2)^{N - 2}$

Plugging cases $$N\in\{1, 2, 3\}$$ into the general formula for the last case reveals

• $$N=1: M\cdot(M - 1)\cdot(M - 2)^{1 - 2}\neq M$$
• $$N=2: M\cdot(M - 1)\cdot(M - 2)^{2 - 2} = M\cdot(M - 1)$$
• $$N=3: M\cdot(M - 1)\cdot(M - 2)^{3 - 2} = M\cdot(M - 1)\cdot(M - 2)$$

This is interesting! This suggests that Case $$N>3$$ really is $$N>1$$! Using Python with its modular exponentiation capabilities of the pow function makes it easy to implement:

def solve(n, m):

q = 1000000007

if n == 1:
return m % q

return (m * (m - 1) * pow(m - 2, n - 2, q)) % q

« Back to problem overview
{"ft_lang_label":"__label__en","ft_lang_prob":0.77205294,"math_prob":0.99984837,"size":2714,"snap":"2022-40-2023-06","text_gpt3_token_len":858,"char_repetition_ratio":0.12177122,"word_repetition_ratio":0.012958963,"special_character_ratio":0.33161387,"punctuation_ratio":0.14384748,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9999379,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2023-01-29T19:50:36Z\",\"WARC-Record-ID\":\"<urn:uuid:a1d1b95f-9e4a-4511-83c5-e9be4c87b8ab>\",\"Content-Length\":\"14189\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:f37e4000-9062-4329-bfd9-3ad3f94ebb9c>\",\"WARC-Concurrent-To\":\"<urn:uuid:7627baef-c3fc-43e4-a800-85477399192f>\",\"WARC-IP-Address\":\"104.21.2.66\",\"WARC-Target-URI\":\"https://www.xarg.org/puzzle/hackerrank/anti-palindromic-strings/\",\"WARC-Payload-Digest\":\"sha1:2JPTKG76GLGNXSYA77EEU5ZPTPJAQWX5\",\"WARC-Block-Digest\":\"sha1:PRPUQWLG3T3QOIKBDFLYXOZM2EAZPNQS\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2023/CC-MAIN-2023-06/CC-MAIN-2023-06_segments_1674764499758.83_warc_CC-MAIN-20230129180008-20230129210008-00167.warc.gz\"}"}