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
My Solution
We can use a StringBuilder to construct the formatted string. We start at the end of the string and add the non-dash characters to the StringBuilder. We also keep track of the number of characters we have added. If the number of characters at any point is divisible by k, we add a dash. Finally at the end remove any leading dash and reverse and return the String. We also must remember to convert lowercase characters to uppercase as we add the characters to the StringBuilder.
Time complexity is O(n), where n is the length of the original string. Space complexity is O(n) due to the space required for the output.
class Solution {
public String licenseKeyFormatting(String s, int k) {
StringBuilder sb = new StringBuilder();
int n = s.length();
int nchar = 0;
for (int i = n-1; i >= 0; i--) {
char c = s.charAt(i);
if (c != '-') {
sb.append(Character.toUpperCase(c));
nchar++;
if (nchar % k == 0) {
sb.append('-');
}
}
}
if (sb.length() > 0 && sb.charAt(sb.length()-1) == '-') {
sb.deleteCharAt(sb.length()-1);
}
return sb.reverse().toString();
}
}