Answer is $4$ Construction part. Consider the binary string $A$, \[A=110100\mid110100\mid \dots \mid 110100 \mid 11\]Notice that $A$ doesn't contains any palindromic substring of length $5$ Bounding part. We will prove that for any binary string always contains palindromic substring of length $4$ Without loss of generality assume that the leftmost digit of binary string $A$ is $1$ Let \[ A = \underbrace{1 \dots 1}_{a_1} \underbrace{0 \dots 0}_{a_2} \dots \underbrace{1 \dots 1}_{a_{2k-1}} \underbrace{0 \dots 0}_{a_{2k}} \dots. \]and define $s_i$ such that $$s_i= a_i+2\min\{a_{i-1},a_{i+1}\}+\dots+2\min\{a_k,a_{2i-k}\}\text{ } \text{if } k\text{ }\text{is the least integer such that }a_k \neq a_{2i-k} $$for example \[A = 1101101 \text{ } \text{then} \text{ } a_1 = 2 , a_2=1 , a_3=2 , a_4=1 , a_5=1 \text{ } \text{and} \text{ } s_1 = 2,s_2=5,s_3=4,s_4=3,s_5=1\] if there exists no such $k$ then sum until it reached leftmost or rightmost Notice the longest length of palindromic substring of $A$ with middle of it is in $a_i$ is equal to $s_i$ Suppose that the longest palindromic substring of $A$ is $3$ Since $a_i \geq 1$ for all $i \in [1,k]$ thus $s_i \geq 3$ for all $i \in [2,k-1]$ $\implies$ $a_i=1$ for all $i \in [2,k-1]$ contradiction since we could find $s_i > 3$.