Frontend School

Longest K-Repeated Substring

DSA
hard

Longest K-Repeated Substring

Hard
String
Hashing
Algorithms

Overview

In many data compression algorithms, pattern matching, and bioinformatics applications, identifying repetitive structures within sequences is crucial. This problem focuses on finding the most significant repetitive pattern in a given text: the longest substring that can be formed by concatenating a smaller, non-empty pattern string P at least k times. This task requires efficient string processing and pattern recognition, essential skills for optimizing data handling in high-performance computing environments.

What you need to do / Task

Your task is to implement a function findLongestKRepeatedSubstring that takes a string text and an integer k as input. The function should identify the longest substring S' of text such that S' can be expressed as P concatenated m times (P^m), where P is a non-empty string and m >= k. If there are multiple such substrings with the same maximum length, you should return the one that appears earliest (has the smallest starting index) in the text. If no such substring exists (e.g., text = "abc", k = 2), return an empty string.

Input & output

  • Input:
    • text: A string consisting of lowercase English letters.
    • k: An integer representing the minimum number of repetitions for the pattern P.
  • Output:
    • A string representing the longest k-repeated substring found according to the rules above. If no such substring exists, return an empty string.

Clarifications

  • A string S' is considered P^m if S' is formed by repeating the non-empty string P exactly m times. For example, "abcabc" is "abc" repeated 2 times.
  • P must be non-empty.
  • If k=1, any substring is P^1. The problem then asks for the longest substring, which would be the entire text.

Examples

1

Example 1

Input:

text = "abcabcabc", k = 2

Output:

"abcabcabc"

Note:

The substring "abcabcabc" can be formed by repeating "abc" 3 times. Since 3 >= k (2), and it's the longest such substring, it's the answer.

2

Example 2

Input:

text = "ababa", k = 2

Output:

"abab"

Note:

The substring "abab" (starting at index 0) can be formed by repeating "ab" 2 times. Its length is 4. The substring "baba" (starting at index 1) can be formed by repeating "ba" 2 times. Its length is also 4. Since "abab" appears earlier in the text (index 0 < index 1), it is the preferred answer.

3

Example 3

Input:

text = "banana", k = 3

Output:

""

Note:

No substring can be formed by repeating a pattern P 3 or more times. For example, "nana" is "na" repeated twice, but 2 < k (3).

Constraints

Constraints & assumptions

  • 1 <= text.length <= 2000
  • 1 <= k <= text.length
  • text consists only of lowercase English letters ('a' through 'z').
  • The solution should be efficient enough to handle text.length = 2000 within typical time limits (e.g., a few seconds).

What interviewers evaluate

  • Correctness: The solution must correctly identify the longest k-repeated substring, handling ties by earliest occurrence, and edge cases.
  • Algorithm Efficiency: The chosen algorithm should be optimal or near-optimal for the given constraints, demonstrating understanding of time and space complexity.
  • Robustness: Proper handling of string indexing, hash collisions (if using hashing), and potential overflow issues.
  • Code Quality: Clean, well-structured, and readable code with appropriate data structures.

Loading editor...