Longest Highly Repeating Substring
LinkedIn's content moderation and recommendation systems often analyze user-generated text, such as profile summaries, job descriptions, or article comments. Identifying frequently recurring patterns can help detect spam, highlight key themes, or even optimize storage by recognizing compressible segments. This problem focuses on finding the most "concentrated" repeating patterns in text.
Your task is to implement a function findLongestHighlyRepeatingSubstring that identifies the longest substring P from a given input string s that appears at least k times. Crucially, all k occurrences of P must be non-overlapping. If multiple substrings satisfy this condition and have the same maximum length, you should return the one that is lexicographically smallest. If no such substring exists, return an empty string.
s: A string representing the text to analyze.k: An integer representing the minimum number of non-overlapping occurrences required.s will not have any repeating substrings.s is not empty and k is 1, the longest substring that appears at least once non-overlapping would simply be the entire string s itself. However, the problem also asks for the lexicographically smallest among longest. This implies that if multiple substrings of the maximum possible length (e.g., length N) exist (which can only happen if N=1 and k=1), the lexicographically smallest should be chosen. For practical purposes, if k=1 and N > 0, the answer will be s itself if N >= 1. If N > 1 and k=1, the problem's constraints length(P) <= s.length / k would imply length(P) <= N. The longest possible substring is s itself. If s is "abcde", k=1, 'a', 'b', 'c', 'd', 'e' all appear once non-overlapping. 'ab', 'bc', etc also appear once. 'abcde' appears once. So the longest is 'abcde'.P occurs starting at index i and another occurrence starts at index j, then j must be greater than or equal to i + length(P).s will consist of lowercase English letters only.Examples
Example 1
Input:
s = "abcabcabc", k = 3
Output:
"abc"
Note:
The substring 'abc' appears 3 times (at indices 0, 3, 6), all non-overlapping. No longer substring appears at least 3 times non-overlapping.
Example 2
Input:
s = "aaaaa", k = 2
Output:
"aa"
Note:
The substring 'aa' appears twice non-overlapping (at indices 0 and 2). 'a' also appears 5 times, but 'aa' is longer. No substring of length 3 or more appears twice non-overlapping.
Example 3
Input:
s = "abracadabra", k = 2
Output:
"abra"
Note:
The substring 'abra' appears twice non-overlapping (at indices 0 and 7). 'a', 'b', 'r', 'ab', 'br', 'ra', 'abr', 'bra' are also valid but shorter. No substring of length 5 or more appears twice non-overlapping.
Constraints
1 <= s.length <= 10^51 <= k <= s.lengths consists only of lowercase English letters ('a'-'z').P will be at most s.length / k. This constraint implicitly limits the maximum possible length for binary search.O(N log N) or O(N log N log N), where N is s.length.O(N).Loading editor...