Smallest Base Segment

Difficulty: Medium

Problem Statement

Amazon's distributed storage network contains critical data represented by a string missingData. Due to synchronization issues, some data segments are unavailable.

To restore the missing data, the system starts with an empty string generatedData and chooses a base segment baseSegment of length segmentSize.

The restoration process works as follows:

1. Create a copy of baseSegment.
2. Append the copied baseSegment to generatedData.
3. Repeat Steps 1 and 2 until, for every character, its frequency in generatedData is greater than or equal to its frequency in missingData.

Your task is to determine the base segment that requires the fewest replications to satisfy the above condition.

If multiple base segments require the same minimum number of replications, return the lexicographically smallest one.

If no such base segment exists, return "-1".

Example 1

Input

segmentSize = 2
missingData = "aavvavv"

Output

"av"

Explanation

The frequencies in missingData are:

a -> 3
v -> 4

Possible base segments of length 2 include:

• "va" → Each replication contributes one 'v' and one 'a'.
  Four replications produce:

a = 4
v = 4

which satisfies the requirement.

• "av" also requires 4 replications.

Any base segment missing either 'a' or 'v' can never satisfy the required frequencies.

Since both "av" and "va" require the same minimum number of replications, the lexicographically smaller string "av" is returned.

Example 2

Input

segmentSize = 4
missingData = "abacbca"

Output

"aabc"

Explanation

The character frequencies are:

a -> 3
b -> 2
c -> 2

Some possible base segments are:

• "aabc" → Requires 2 replications.
• "abbc" → Requires 3 replications.
• "abcc" → Requires 3 replications.

Among all valid choices, "aabc" requires the fewest replications. It is also the lexicographically smallest optimal solution.

Parameters

• int segmentSize — Length of the base segment.
• string missingData — String representing the missing data.

Returns

Return the lexicographically smallest base segment of length segmentSize whose repeated copies satisfy the frequency requirements of missingData.

Return "-1" if no valid base segment exists.

Constraints

• 1 <= segmentSize <= 2 × 10^5
• 1 <= missingData.length <= 2 × 10^5
• missingData consists only of lowercase English letters ('a'–'z').