Shortest Palindromic Substring | Function return the shortest palindromic substring ; One by one consider every character as center point of even and length palindromes ; Find the longest odd length palindrome with center point as i ; Find the even length palindrome with center points as i - 1 and i . ; Smallest substring which is not empty ; Driver code
def ShortestPalindrome ( s ) : NEW_LINE INDENT n = len ( s ) NEW_LINE v = [ ] NEW_LINE for i in range ( n ) : NEW_LINE INDENT l = i NEW_LINE r = i NEW_LINE ans1 = " " NEW_LINE ans2 = " " NEW_LINE while ( ( l >= 0 ) and ( r < n ) and ( s [ l ] == s [ r ] ) ) : NEW_LINE INDENT ans1 += s [ l ] NEW_LINE l -= 1 NEW_LINE r += 1 NEW_LINE DEDENT l = i - 1 NEW_LINE r = i NEW_LINE while ( ( l >= 0 ) and ( r < n ) and ( s [ l ] == s [ r ] ) ) : NEW_LINE INDENT ans2 += s [ l ] NEW_LINE l -= 1 NEW_LINE r += 1 NEW_LINE DEDENT v . append ( ans1 ) NEW_LINE v . append ( ans2 ) NEW_LINE DEDENT ans = v [ 0 ] NEW_LINE for i in range ( len ( v ) ) : NEW_LINE INDENT if ( v [ i ] != " " ) : NEW_LINE INDENT ans = min ( ans , v [ i ] ) NEW_LINE DEDENT DEDENT return ans NEW_LINE DEDENT s = " geeksforgeeks " NEW_LINE print ( ShortestPalindrome ( s ) ) NEW_LINE