Maximum Product Of The Length Of Two Palindromic Substrings
01 · Problem
Given a string s, choose two substrings s[i..j] and s[k..l] (inclusive, 0-indexed) such that:
- both substrings are palindromes,
- both have odd length, and
- they do not overlap, i.e.
j < k.
Return the maximum possible value of length1 * length2. Since any single character is an odd-length palindrome and s has at least two characters, an answer always exists (at least 1).
02 · Examples
s = "abaxyzyx"
15
Take "aba" (indices 0-2, length 3) and "xyzyx" (indices 3-7, length 5). They do not overlap, so the product is 3 * 5 = 15.
s = "racecarxlevel"
35
Take "racecar" (length 7) and "level" (length 5); they are separated by "x". Product 7 * 5 = 35.
s = "abc"
1
No odd palindrome longer than 1 exists, so pick any two single characters: 1 * 1 = 1.
03 · Constraints
- 012 <= s.length <= 105
- 02s consists only of lowercase English letters
- 03Both chosen substrings must have odd length and must not overlap; the answer is at most (n/2)^2 and fits in a 64-bit integer
04 · Optimal complexity
- Time
- O(n)
- Space
- O(n)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.