Sponsored
Sponsored
This 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.
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.
1def licenseKeyFormatting(s, k):
2 s = s.replace('-', '').upper()
3 n = len(s)
4 remainder = n % k
5 groups = []
6 # First group
7 if remainder:
8 groups.append(s[:remainder])
9 # Other groups
10 for i in range(remainder, n, k):
11 groups.append(s[i:i+k])
12 return '-'.join(groups)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.
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.
Time Complexity: O(n), where n is the length of s. Space Complexity: O(n) for storing the result string temporarily.
1#include <algorithm>
2#include <cctype>
3#include <string>
4using namespace std;
5
6string licenseKeyFormatting(string s, int k) {
string res;
int count = 0;
for (auto it = s.rbegin(); it != s.rend(); ++it) {
if (*it != '-') {
if (count == k) {
res += '-';
count = 0;
}
res += toupper(*it);
count++;
}
}
reverse(res.begin(), res.end());
return res;
}The C++ solution also follows the same reverse approach. It iterates over the string in reverse, processes each character, and uses a counter to determine when to insert a dash.