You are given a license key represented as a string s that consists of only alphanumeric characters and dashes. The string is separated into n + 1 groups by n dashes. You are also given an integer k.
We want to reformat the string s such that each group contains exactly k characters, except for the first group, which could be shorter than k but still must contain at least one character. Furthermore, there must be a dash inserted between two groups, and you should convert all lowercase letters to uppercase.
Return the reformatted license key.
Example 1:
Input: s = "5F3Z-2e-9-w", k = 4 Output: "5F3Z-2E9W" Explanation: The string s has been split into two parts, each part has 4 characters. Note that the two extra dashes are not needed and can be removed.
Example 2:
Input: s = "2-5g-3-J", k = 2 Output: "2-5G-3J" Explanation: The string s has been split into three parts, each part has 2 characters except the first part as it could be shorter as mentioned above.
Constraints:
1 <= s.length <= 105s consists of English letters, digits, and dashes '-'.1 <= k <= 104This approach involves first cleaning up the input string by removing all non-alphanumeric characters and converting it to uppercase. Then, starting from the end of the string, we build the new license key by appending groups of size k. This is achieved using a StringBuilder for efficient string manipulation.
We begin by removing all dashes and converting the string to uppercase. We calculate the remainder, which helps in determining the first group size that could be less than k. We use a loop to iterate through the cleaned-up string in steps of k and store these groups. Finally, we join the groups with a dash and return the result.
JavaScript
Time Complexity: O(n), where n is the length of the string s. Space Complexity: O(n) due to the additional storage requirements for the new formatted string.
This method suggests reversing the cleaned-up string to easily extract groups from the end, and then reversing the result at the end. This eliminates the need for calculating the remainder at the start and allows straightforward appending of characters.
By reversing the process, we simplify grouping into steps of k directly from the end without needing any special handling for the first group. We maintain a counter to insert a dash after every k characters and finally reverse the accumulated result.
C++
Time Complexity: O(n), where n is the length of s. Space Complexity: O(n) for storing the result string temporarily.
| Approach | Complexity |
|---|---|
| Iterative Approach with StringBuilder | Time Complexity: O(n), where n is the length of the string |
| Reverse and Append Approach | Time Complexity: O(n), where n is the length of |
License Key Formatting • Kevin Naughton Jr. • 16,106 views views
Watch 9 more video solutions →Practice License Key Formatting with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor