Given a string s , return the longest substring of s that reads the same forwards and backwards. If several substrings share the maximum length, return the one that appears first (smallest starting index). Input format Input is [s] , e.g. [ babad ] .