482. License Key Formatting
Description
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 <= 105
s
consists of English letters, digits, and dashes'-'
.1 <= k <= 104
Solutions
Solution 1: Simulation
First, we count the number of characters in the string $s$ excluding the hyphens, and take the modulus of $k$ to determine the number of characters in the first group. If it is $0$, then the number of characters in the first group is $k$; otherwise, it is the result of the modulus operation.
Next, we iterate through the string $s$. For each character, if it is a hyphen, we skip it; otherwise, we convert it to an uppercase letter and add it to the answer string. Meanwhile, we maintain a counter $cnt$, representing the remaining number of characters in the current group. When $cnt$ decreases to $0$, we need to update $cnt$ to $k$, and if the current character is not the last one, we need to add a hyphen to the answer string.
Finally, we remove the hyphen at the end of the answer string and return the answer string.
The time complexity is $O(n)$, where $n$ is the length of the string $s$. Ignoring the space consumption of the answer string, the space complexity is $O(1)$.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
|