TIFR CSE 2024 | Part A | Question: 8

Question

A palindrome is a string that reads the same in reverse (e.g. ABBA or KAYAK or MALAYALAM).
How many strings of length 5 using the letters from $\{A, B, C, D, E\}$ have no palindromic substring of length at least 2?

• A. $243$
• B. $405$
• C. $540$
• D. $675$
• E. $1280$

   

Answer 1

for a string $s$ , notice that for any index $i$ the following cases

1. if $s[i] = s[i+1]$, then we will have a palindromic substring of length 2 . so 2 adjacent characters have to be different always
2. if $s[i] = s[i+2]$, then we will have a palindromic substring of length 3 . so 3 adjacent characters have to be different always because $i,i+1$ form the 1st case and $i,i+2$ form the 2nd case

so using this we get our base case , $f(3) = \text{select 3 diff characters and permute them} = \binom{5}{3}\times3!$

$\small{f(n) = (\text{nth char we add should be } s[n] \neq s[n-1] \neq s[n-2] \text{ from 1,2} ) = \text{3 choices for nth char} = f(n-1)\cdot3}$

$f(5) = f(4)\times3 = f(3) \times 3 \times 3 = \binom{5}{3}\times3!\times 3 \times 3 = 540$

so ans is C i.e. 540