Frontend School

K-th Lexicographical Palindromic Substring

DSA
hard

K-th Lexicographical Palindromic Substring

Hard
String
Palindrome
Sorting
Hashing

Overview

In text processing and bioinformatics, identifying and analyzing palindromic structures is crucial. For instance, in genomics, palindromic sequences often indicate specific functional regions. This problem challenges you to efficiently find and order these significant substrings. You will be given a string and an integer K, and your task is to retrieve the K-th lexicographically smallest distinct palindromic substring.

What you need to do / Task

Your task is to implement the function findKthLexicographicalPalindrome which takes a string s and an integer k as input.

  1. Identify all palindromic substrings present in s.
  2. From these, collect only the distinct palindromic substrings.
  3. Sort these distinct palindromic substrings lexicographically (alphabetical order).
  4. Return the k-th substring from this sorted list.
  5. If k is greater than the total number of distinct palindromic substrings, return an empty string.

Input & output

Function Signature:

function findKthLexicographicalPalindrome(s: string, k: number): string;
  • s: The input string, consisting of lowercase English letters.
  • k: An integer representing the 1-based index of the desired palindrome (e.g., k=1 for the first, k=2 for the second).

Return Value:

  • A string representing the k-th lexicographically smallest distinct palindromic substring.
  • An empty string "" if k is out of bounds.

Clarifications

  • Distinctness: Two palindromic substrings are considered distinct if their string values are different, regardless of their starting or ending positions in s. For example, in "abaaba", "aba" appears twice, but it's counted as one distinct palindrome.
  • Lexicographical Order: Standard dictionary order. "a" < "aa" < "aab" < "b".
  • 1-based indexing: k refers to the 1st, 2nd, ..., K-th element.

Examples

1

Example 1

Input:

s = "abaaba", k = 3

Output:

"aba"

Note:

Distinct palindromes from "abaaba": "a", "b", "aa", "aba", "baa", "abaaba". Sorted lexicographically: ["a", "aa", "aba", "abaaba", "b", "baa"]. The 3rd element is "aba".

2

Example 2

Input:

s = "abacaba", k = 4

Output:

"aca"

Note:

Distinct palindromes from "abacaba": "a", "b", "c", "aba", "aca", "bab", "bacab", "abacaba". Sorted lexicographically: ["a", "aba", "abacaba", "aca", "b", "bab", "bacab", "c"]. The 4th element is "aca".

3

Example 3

Input:

s = "topcoder", k = 10

Output:

""

Note:

Distinct palindromes from "topcoder": "c", "d", "e", "o", "p", "r", "t". (All single characters are palindromes). There are only 7 distinct palindromes. Since k=10 is out of bounds, an empty string is returned.

Constraints

Constraints & assumptions

  • 1 <= s.length <= 2000
  • 1 <= k <= 10^9
  • s consists only of lowercase English letters ('a'-'z').
  • Time complexity target: O(N^2 log N) where N is s.length.
  • Space complexity target: O(N^2).

Out of scope

  • Handling non-alphabetic characters or mixed case.
  • Optimizations beyond O(N^2 log N) for N=2000 (e.g., using Palindromic Trees for linear distinct palindrome extraction, which is typically too complex for a 40-minute interview unless specifically prompted).

What interviewers evaluate

  • Ability to correctly identify all palindromic substrings.
  • Correctly handling distinctness for palindromic substrings.
  • Efficient implementation of lexicographical sorting.
  • Overall algorithm efficiency (time and space complexity).
  • Code clarity, edge case handling (e.g., k out of bounds), and robust error handling.

Loading editor...