Smallest Repeating Segment

Hardbinary search on answergreedycounting 00:00

Data recovery: a segment of length segmentSize (lowercase letters) will be copied t times and concatenated. The concatenation must contain at least as many of each letter as appears in missingData (order doesn't matter).

Choose the segment that needs the fewest copies t. Among those, return the lexicographically smallest segment. If impossible, return "-1".

Signature

getSmallestBaseSegment(segmentSize: int, missingData: string) → string

Example 1

segmentSize = 4

missingData = "aaabbcc"

output = "aabc"

t=2 needs ceil(3/2)+ceil(2/2)+ceil(2/2) = 4 slots → counts a2 b1 c1 → 'aabc'

Example 2

segmentSize = 3

missingData = "aab"

output = "aab"

t=1 fits exactly: 'aab'

Example 3

segmentSize = 2

missingData = "abc"

output = "-1"

3 distinct letters can't fit in 2 slots → '-1'

Constraints

1 ≤ segmentSize ≤ 2·10^5
1 ≤ |missingData| ≤ 2·10^5

⌘/Ctrl + Enter runs examples

Run checks the examples. Submit runs every hidden test (21, including large inputs that catch slow solutions).