Find the longest palindromic substring
Company: TikTok
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
Quick Answer: This question evaluates proficiency in string manipulation and algorithmic problem-solving, focusing on palindrome detection and substring handling within the Coding & Algorithms domain.
Constraints
- 1 <= len(s) <= 2000
- s contains only ASCII letters and digits
- The substring must be contiguous
Examples
Input: "babad"
Expected Output: "bab"
Explanation: Both "bab" and "aba" are valid longest palindromes of length 3. This solution keeps the first one it finds, which is "bab".
Input: "cbbd"
Expected Output: "bb"
Explanation: The longest palindromic substring is the even-length palindrome "bb".
Input: "a"
Expected Output: "a"
Explanation: A single character is always a palindrome.
Input: "ac"
Expected Output: "a"
Explanation: There are no palindromes longer than length 1. This solution returns the first one, "a".
Input: "forgeeksskeegfor"
Expected Output: "geeksskeeg"
Explanation: "geeksskeeg" is the longest palindromic substring.
Input: "aaaa"
Expected Output: "aaaa"
Explanation: The entire string is a palindrome.
Hints
- A palindrome can be expanded outward from its center. Try considering both odd-length and even-length centers.
- For each index, check the longest palindrome centered at that index and between that index and the next one.