370. Longest and Lexicographically Greatest Palindromic Substrings

Longest and Lexicographically Greatest Palindromic Substrings

Given a string s, find its longest palindromic substring. A substring is palindromic when it reads the same from left to right and right to left.

Implement one method that returns the first longest palindromic substring and another method that resolves ties by returning the lexicographically greatest longest palindromic substring.

Longest and Lexicographically Greatest Palindromic Substrings

Longest Palindromic Substring

String longestPalindrome(String s)

s is the string to examine.
The method returns a longest palindromic substring of s.
If multiple longest palindromic substrings exist, return the one with the smallest starting index.

Lexicographically Greatest Longest Palindromic Substring

String greatestLongestPalindrome(String s)

s is the string to examine.
The method returns a longest palindromic substring of s.
If multiple longest palindromic substrings exist, return the lexicographically greatest one.

Palindrome Rules

A substring consists of consecutive characters from s.
A substring is palindromic when it reads the same in both directions.
A single character is always a palindrome.
Lexicographical comparison follows the natural order of lowercase English letters.

Constraints

1 ≤ s.length() ≤ 1,000
s contains only lowercase English letters.

Examples

Example 1

longestPalindrome(s = "abacdc")

Output: "aba"

Both "aba" and "cdc" are longest palindromic substrings of length 3. The first method returns "aba" because it has the smaller starting index.

Example 2

greatestLongestPalindrome(s = "abacdc")

Output: "cdc"

Both longest palindromic substrings have length 3. "cdc" is returned because it is lexicographically greater than "aba".

Example 3

longestPalindrome(s = "noonabbax")

Output: "noon"

The longest palindromic substrings are "noon" and "abba". The substring "noon" starts first.

Example 4

greatestLongestPalindrome(s = "noonabbax")

Output: "noon"

Both candidates have length 4, and "noon" is lexicographically greater than "abba".

Example 5

longestPalindrome(s = "forgeeksskeegfor")

Output: "geeksskeeg"

"geeksskeeg" is the unique longest palindromic substring.

Example 6

greatestLongestPalindrome(s = "algorithm")

Output: "t"

No palindrome longer than one character exists. Among all single-character palindromes, "t" is lexicographically greatest.