482. License Key Formatting
Model: qwen2.5-coder:14b
Topics:
FAANG asked: 0
Acceptance rate: 43.1%
Problem Breakdown
The problem requires us to reformat a given license key string S according to specific rules. The input consists of a string S containing alphanumeric characters and dashes (-). The goal is to split the string into groups such that each group contains exactly K characters, except for possibly the first group which can be shorter but must contain at least one character. Additionally, all lowercase letters should be converted to uppercase, and there must be a dash inserted between two groups.
Inputs:
- A non-empty string
Sconsisting of alphanumeric characters and dashes. - An integer
Krepresenting the size of each group.
Outputs:
- A reformatted string with groups of
Kcharacters separated by dashes.
Implicit Constraints or Tricky Edge Cases:
- The first group can be shorter than
K. - The string may contain leading or trailing dashes that need to be ignored.
- The string could be entirely made up of dashes, resulting in an empty output after removing them.
- The length of the string
Swill not exceed 12,000 characters.
Intuition
A brute-force approach would involve iterating through the string and manually constructing groups while handling the conversion to uppercase. However, this approach is inefficient due to its complexity and potential for errors in edge case handling.
The key insight is to first remove all dashes from the string and convert it to uppercase. Then, we can start forming groups of K characters from the end of the string towards the beginning. This way, we ensure that the first group can be shorter than K if necessary, and we handle the grouping in a straightforward manner.
Approach
-
Remove Dashes and Convert to Uppercase:
- Iterate through the string
Sand build a new string without dashes. - Convert all characters to uppercase during this process.
- Iterate through the string
-
Form Groups of K Characters:
- Initialize an empty list to store the groups.
- Starting from the end of the cleaned string, take chunks of up to
Kcharacters at a time. - Append each chunk to the list of groups.
-
Join Groups with Dashes:
- Reverse the list of groups to maintain the correct order.
- Join the groups using dashes and return the resulting string.
Complexity Analysis
- Time Complexity: O(n), where n is the length of the input string
S. We iterate through the string a constant number of times. - Space Complexity: O(n), as we store the cleaned string and the list of groups, both of which can be up to the length of the input string.
Solution
def licenseKeyFormatting(S: str, K: int) -> str:
# Step 1: Remove dashes and convert to uppercase
cleaned = ''.join(c.upper() for c in S if c != '-')
# Step 2: Form groups of K characters from the end
groups = []
while cleaned:
groups.append(cleaned[-K:])
cleaned = cleaned[:-K]
# Step 3: Join groups with dashes and return
return '-'.join(reversed(groups))
Edge Cases Handled
- Empty Input: The input string
Sis guaranteed to be non-empty, so this case does not apply. - All Dashes: If the input string contains only dashes, the cleaned string will be empty, resulting in an empty output after joining groups.
- Single Character Groups: If the length of the cleaned string is less than or equal to
K, the first group will naturally be shorter thanK. - Leading/Trailing Dashes: These are ignored during the cleaning process, ensuring they do not affect the final output.