Get Smallest Base Segment
Learn this problemProblem statement
In Amazon's distributed storage network, some critical data segments are missing. They are represented by a string missingData. The system restores data by choosing a base segment of length segmentSize and repeatedly appending copies of that base segment to a generated string.
A base segment is valid if, after some number of replications, the generated string contains every character in missingData at least as many times as it appears in missingData.
Among all valid base segments, choose one that requires the fewest replications. If more than one base segment requires that same minimum number of replications, return the lexicographically smallest one. If no valid base segment exists, return "-1".
Function
getSmallestBaseSegment(segmentSize: int, missingData: String) → StringComplete the function getSmallestBaseSegment.
getSmallestBaseSegment has the following parameters:
int segmentSize: the length of the base segment that can be replicatedString missingData: a string representing the missing data segments
Returns
String: the lexicographically smallest valid base segment of length segmentSize that minimizes the required number of replications, or "-1" if no such segment exists.
Examples
Example 1
segmentSize = 2missingData = "aavvavv"return = "av"The character a appears 3 times and v appears 4 times. Both "av" and "va" require 4 replications. Since "av" is lexicographically smaller, it is returned.
Example 2
segmentSize = 1missingData = "abc"return = "-1"A base segment of length 1 can contain only one distinct character, so it cannot generate all three required characters.
Constraints
1 <= segmentSize <= missingData.lengthmissingDataconsists of lowercase English letters.
More Amazon problems
- Shortest Distance on a Circular Bus RouteOA · Seen Jul 2026
- Longest Increasing Subsequence With Bounded Adjacent DifferenceONSITE INTERVIEW · Seen Jul 2026
- Search in a Rotated Sorted ArrayONSITE INTERVIEW · Seen Jul 2026
- Sliding Window MaximumONSITE INTERVIEW · Seen Jul 2026
- Merge IntervalsOA · Seen Jul 2026
- Sort Bug Report FrequenciesOA · Seen Jul 2026
- Drone Delivery RouteOA · Seen Jul 2026
- First Valid Word SegmentationONSITE INTERVIEW · Seen Jul 2026