Frontend School

Most Frequent Length-Constrained Palindromic Substring

DSA
hard

Most Frequent Length-Constrained Palindromic Substring

Hard
String

Overview

In text processing, bioinformatics, and pattern recognition, identifying specific types of repeated patterns within sequences is crucial. Palindromic substrings, which read the same forwards and backwards, are a common and significant class of such patterns. This problem challenges you to find the most prominent palindromic substring in a given text, considering both its frequency and minimum length, and applying specific tie-breaking rules.

What you need to do / Task

Implement the function mostFrequentPalindrome that takes a string s and an integer L as input. Your task is to:

  1. Identify all distinct palindromic substrings within s.
  2. Count the total occurrences of each distinct palindromic substring within s.
  3. Filter these palindromes, considering only those whose length is at least L.
  4. From the filtered set, find the palindrome that appears most frequently.
  5. If there are multiple palindromes with the same maximum frequency, return the one that is lexicographically smallest.
  6. If no palindromic substring satisfies the length constraint L, return an empty string "".

Input & output

  • s: string: The input string consisting of lowercase English letters.
  • L: number: An integer representing the minimum required length for a palindromic substring to be considered.
  • Returns string: The most frequent palindromic substring satisfying the conditions, or an empty string if none exist.

Clarifications

  • An empty string "" is not considered a palindrome in this problem context.
  • A single character is a palindrome (e.g., 'a').
  • Lexicographical comparison: 'a' < 'ab' < 'b'. If 'aa' and 'b' have the same max frequency, 'aa' is smaller.

Examples

1

Example 1

Input:

s = "abacaba", L = 2

Output:

"aba"

Note:

Palindromes of length >= 2: 'aba' (2 occurrences), 'aca' (1), 'bab' (1), 'bacab' (1), 'abacaba' (1). 'aba' is the most frequent.

2

Example 2

Input:

s = "aaaaa", L = 3

Output:

"aaa"

Note:

Palindromes of length >= 3: 'aaa' (3 occurrences), 'aaaa' (2), 'aaaaa' (1). 'aaa' is the most frequent.

3

Example 3

Input:

s = "topcoderopen", L = 1

Output:

"o"

Note:

All single characters are palindromes. 'o' appears 3 times, 'e' and 'p' appear 2 times. 'o' is the most frequent and lexicographically smallest among tied maximal frequencies.

4

Example 4

Input:

s = "racecar", L = 8

Output:

""

Note:

No palindrome in 'racecar' has a length of 8 or more. The longest is 'racecar' itself, with length 7.

5

Example 5

Input:

s = "zzzaacccaaa", L = 2

Output:

"aa"

Note:

Palindromes of length >= 2 and their frequencies: 'zz' (2), 'aa' (3), 'cc' (2), 'aaa' (1), 'ccc' (1), 'zzz' (1). 'aa' is the most frequent.

Constraints

Constraints & assumptions

  • 1 <= s.length <= 10^5
  • s consists only of lowercase English letters ('a'-'z').
  • 1 <= L <= s.length

What interviewers evaluate

  • Algorithmic Correctness: The solution must accurately identify all palindromes, count their frequencies, and apply tie-breaking rules correctly.
  • Efficiency: The solution should demonstrate optimal or near-optimal time and space complexity for the given constraints.
  • Edge Case Handling: Correctly handles scenarios such as L being greater than any palindrome's length, or strings with no repeated palindromes.
  • Code Quality: Clarity, structure, and readability of the implementation.

Loading editor...