482. License Key Formatting
Problem Description
You are provided with a string s
representing a license key. This string only contains alphanumeric characters (letters and numbers) and dashes -
. The string is split into n + 1
segments by n
dashes. You are also given an integer k
.
The goal is to reformat the license key in such a way that each segment contains exactly k
characters, except possibly for the first segment, which can be shorter but must contain at least one character. Additionally, each group must be separated by a single dash, and all lowercase letters should be converted to uppercase.
The task is to transform the string s
into a new string that meets these requirements and to return the reformatted license key.
Intuition
To solve this problem, the solution has to process the string and reformat it according to the given rules. Here's the step-by-step reasoning behind the solution approach:
-
First, we simplify our given string by removing all the dashes from it. This allows us to start with only alphanumeric characters, making it easier to handle the grouping.
-
We convert all lowercase letters to uppercase since the final output should be in uppercase, as specified in the rules.
-
We need to deal with the requirement that the first group can be shorter than the others. To manage this, we calculate the length of the first group, which is the remainder of the length of the string after removing all the dashes, modulo
k
. If this remainder is zero, it means the string's length is a multiple ofk
, so the first group should also bek
characters long. -
We iterate over the characters of the now dash-less and uppercase string, adding each character to a results list.
-
While doing this, we keep count of the number of characters added since the last dash or the start of the string. When this count reaches the length of the current group (which starts as the length of the first group), we add a dash to the results list (except after the final character).
-
After adding a dash, we reset the count and also set the group length to
k
for all groups that will be processed after the first. -
Once we finish processing all characters, we join the characters in the results list into a single string, which is our reformatted license key.
By following these steps, we arrive at a reformatted string that satisfies all the specified conditions for the license key formatting problem.
Solution Approach
The implementation of the reformatted license key solution uses basic string manipulation techniques and list operations to conform to the desired formatting rules. Here's a breakdown of how the code achieves this:
-
s = s.replace('-', '').upper()
: The first line of the method removes all dashes from the input strings
usingreplace('-', '')
and converts all lowercase letters to uppercase withupper()
. This simplifies the string so that we only deal with alphanumeric characters. -
res = []
: A new listres
is initialized to keep track of the characters for the final result. Lists in Python provide efficient append operations which are used later in the code to construct the reformatted string step by step. -
cnt = (len(s) % k) or k
: This line sets the initial group's length. If there is a remainder when dividing the string's length byk
, this remainder will determine the length of the first group; otherwise, the first group will also bek
characters long. This is handled by using the logicalor
which returnsk
iflen(s) % k
is zero. -
t = 0
: A variablet
is initialized to keep a count of how many characters have been processed since the last dash was added tores
or since the start. -
The code then iterates over the characters in the processed string:
for i, c in enumerate(s)
: Theenumerate
function is used to get both the indexi
and the characterc
during iteration.res.append(c)
: Each character is appended tores
.t += 1
: The countert
is incremented with each character added.
-
The following conditional block checks if the current group is complete:
if t == cnt
: Ift
equals the current group lengthcnt
, it means a group is complete, and a dash should be added, unless it's the last group.- Inside the conditional block:
t = 0
: The counter is reset for the next group.cnt = k
: From now on, every group will havek
characters as the first group condition has been satisfied.if i != len(s) - 1
: A dash is appended tores
only if the current character is not the last one to prevent a trailing dash.
-
Finally,
''.join(res)
: The contents of the listres
are combined usingjoin
to form the reformatted license key as a single string.
The enumerate
function aids in keeping track of both the index and the character simultaneously; conditional statements control the logic for when to add dashes and reset the counter, and the list's property of dynamic resizing helps efficiently build the output string without worrying about preallocating the exact size of the resultant string.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with a small example. Suppose the input string s
is "2-4A0r7-4k" and the integer k
is 4.
-
First, we remove all the dashes from
s
and convert it to uppercase: "24A0R74K". -
Then we initialize an empty list
res
to hold the reformatted characters, and we calculate the length of the first group. The length of "24A0R74K" is 8 andk
is 4. So, the length for the first group will belen(s) % k
, which is 0. Since the remainder is 0, our first group will also be 4 characters long (equal tok
). -
We start iterating over "24A0R74K". Initialize
t
to 0 for the count of characters. -
As we iterate, we append each character to
res
and incrementt
. -
After adding 4 characters ("24A0"), since
t
equalscnt
(both are 4), we append a dash tores
given that we are not at the end of the string. We resett
to 0 and setcnt
tok
for all following groups. -
We continue appending characters to
res
and oncet
again equalsk
, we append another dash. This process continues until all characters have been processed. -
We join the elements of
res
with''
to get our final reformatted string. In this case, "24A0-R74K".
Through these steps, following the solution approach, the input string is reformatted to "24A0-R74K", where each group has exactly k
characters, except the first one (if needed), and all characters are in uppercase, separated by dashes. This satisfies all the conditions for the problem.
Solution Implementation
1class Solution:
2 def licenseKeyFormatting(self, s: str, k: int) -> str:
3 # Remove all the hyphens from the string and convert to uppercase.
4 s = s.replace('-', '').upper()
5
6 # Initialize an empty list to store the formatted license key.
7 formatted_license_key = []
8
9 # Calculate the number of characters before the first dash.
10 first_group_length = (len(s) % k) or k
11
12 # Initialize a count variable to keep track of the characters added in the current group.
13 count = 0
14
15 # Iterate over the characters in the modified string.
16 for index, char in enumerate(s):
17 # Append the current character to the formatted_license_key list.
18 formatted_license_key.append(char)
19 count += 1
20
21 # Check if the current group has reached its required length.
22 if count == first_group_length:
23 # Reset count for the next group.
24 count = 0
25 # Update first_group_length to k as all subsequent groups should be of length k.
26 first_group_length = k
27 # Append a dash if the current character is not the last one.
28 if index != len(s) - 1:
29 formatted_license_key.append('-')
30
31 # Join the list into a string and return the formatted license key.
32 return ''.join(formatted_license_key)
33
1class Solution {
2 public String licenseKeyFormatting(String s, int k) {
3 // Remove all hyphens and convert to upper case letters
4 s = s.replace("-", "").toUpperCase();
5
6 // StringBuilder to hold the formatted license key
7 StringBuilder formattedKey = new StringBuilder();
8
9 // Initialize count for tracking group sizes
10 int count = 0;
11
12 // Calculate the initial size for the first group if it's not of length k
13 int firstGroupLength = s.length() % k;
14 if (firstGroupLength == 0) {
15 firstGroupLength = k; // If modulus is 0, the first group is of full length k
16 }
17
18 // Iterate over each character in the stripped license key
19 for (int i = 0; i < s.length(); ++i) {
20 // Append the current character to the StringBuilder
21 formattedKey.append(s.charAt(i));
22 ++count; // Increment the character count for the current group
23
24 // If the current count reaches the firstGroupLength or k,
25 // it indicates the end of a group
26 if (count == firstGroupLength) {
27 count = 0; // Reset the count for the next group
28 firstGroupLength = k; // All subsequent groups will be of length k
29
30 // Append a hyphen if this is not the last character
31 if (i != s.length() - 1) {
32 formattedKey.append('-');
33 }
34 }
35 }
36
37 // Convert the StringBuilder to a String and return the formatted license key
38 return formattedKey.toString();
39 }
40}
41
1class Solution {
2public:
3 string licenseKeyFormatting(string S, int K) {
4 // Remove hyphens and convert characters to uppercase
5 string formattedString = "";
6 for (char c : S) {
7 if (c != '-') { // Skip hyphens
8 if ('a' <= c && c <= 'z') { // Convert lowercase to uppercase
9 c += 'A' - 'a';
10 }
11 formattedString += c;
12 }
13 }
14
15 // Calculate the size of the first group of characters
16 int firstGroupSize = formattedString.size() % K;
17 if (firstGroupSize == 0) {
18 firstGroupSize = K; // If the entire string is a multiple of K, use K instead
19 }
20
21 // Initialize counter
22 int counter = 0;
23
24 // Build the resulting formatted key string
25 string result = "";
26 for (int i = 0; i < formattedString.size(); ++i) {
27 result += formattedString[i]; // Add the next character to the result
28 counter++; // Increment the counter
29
30 // Check if we reach the end of a group
31 if (counter == firstGroupSize) {
32 counter = 0; // Reset the counter for the next group
33 firstGroupSize = K; // After the first group, all groups will be of size K
34 if (i != formattedString.size() - 1) { // If this isn't the last character
35 result += '-'; // Add a hyphen
36 }
37 }
38 }
39
40 return result; // Return the resulting formatted license key
41 }
42};
43
1// Function to format the license key
2function licenseKeyFormatting(S: string, K: number): string {
3 // Remove hyphens and convert characters to uppercase
4 let formattedStringArray: string[] = [];
5 for (let c of S) {
6 if (c !== '-') { // Skip hyphens
7 if (c >= 'a' && c <= 'z') { // Convert lowercase to uppercase
8 c = c.toUpperCase();
9 }
10 formattedStringArray.push(c);
11 }
12 }
13
14 let formattedString: string = formattedStringArray.join('');
15
16 // Calculate the size of the first group of characters
17 let firstGroupSize: number = formattedString.length % K;
18 if (firstGroupSize === 0) {
19 firstGroupSize = K; // If the entire string is a multiple of K, use K instead
20 }
21
22 // Initialize counter
23 let counter: number = 0;
24
25 // Build the resulting formatted key string
26 let resultArray: string[] = [];
27 for (let i = 0; i < formattedString.length; ++i) {
28 resultArray.push(formattedString[i]); // Add the next character to the result
29 counter++; // Increment the counter
30
31 // Check if we reach the end of a group
32 if (counter === firstGroupSize) {
33 counter = 0; // Reset the counter for the next group
34 firstGroupSize = K; // After the first group, all groups will be of size K
35 if (i !== formattedString.length - 1) { // If this isn't the last character
36 resultArray.push('-'); // Add a hyphen
37 }
38 }
39 }
40
41 return resultArray.join(''); // Return the resulting formatted license key
42}
43
Time and Space Complexity
Time Complexity
The time complexity of the function can be analyzed by looking at the number of operations it performs relative to the size of the input, s
. The function consists of the following main steps:
-
Removing dashes and converting the string to upper case: Both of these operations (
s.replace('-', '')
ands.upper()
) iterate over the entire string once, which has a time complexity ofO(N)
whereN
is the length of the strings
. -
The loop that builds the final formatted string: This loop goes through each character in the string
s
one time, and the operations inside the loop are constant-time operations. Therefore, this loop also has a time complexity ofO(N)
.
Since both steps are sequentially executed and both have a linear complexity in terms of N
, the overall time complexity is O(N) + O(N)
, which simplifies to O(N)
.
Space Complexity
The space complexity of the function is determined by the amount of additional memory used as the size of the input varies. In this case:
-
The
res
list is the main additional data structure which holds the reformatted license key. At most, this will hold the same number of alphanumeric characters as the originals
with the addition of the dashes necessary for formatting. In the worst-case scenario, when no dashes are to be removed from the input, the length ofres
would belen(s) + len(s)//k
, considering an additional dashlen(s)//k
times. Therefore, the space complexity isO(N + N//k)
which is equivalent toO(N)
whereN
is the length of the strings
. -
The
cnt
andt
variables are integer counters with constant space, so they contributeO(1)
.
Combining the above points, the total space complexity would be O(N)
for the res
array and O(1)
for the other variables, leading to an overall space complexity of O(N)
.
Learn more about how to find time and space complexity quickly using problem constraints.
What does the following code do?
1def f(arr1, arr2):
2 i, j = 0, 0
3 new_arr = []
4 while i < len(arr1) and j < len(arr2):
5 if arr1[i] < arr2[j]:
6 new_arr.append(arr1[i])
7 i += 1
8 else:
9 new_arr.append(arr2[j])
10 j += 1
11 new_arr.extend(arr1[i:])
12 new_arr.extend(arr2[j:])
13 return new_arr
14
1public static List<Integer> f(int[] arr1, int[] arr2) {
2 int i = 0, j = 0;
3 List<Integer> newArr = new ArrayList<>();
4
5 while (i < arr1.length && j < arr2.length) {
6 if (arr1[i] < arr2[j]) {
7 newArr.add(arr1[i]);
8 i++;
9 } else {
10 newArr.add(arr2[j]);
11 j++;
12 }
13 }
14
15 while (i < arr1.length) {
16 newArr.add(arr1[i]);
17 i++;
18 }
19
20 while (j < arr2.length) {
21 newArr.add(arr2[j]);
22 j++;
23 }
24
25 return newArr;
26}
27
1function f(arr1, arr2) {
2 let i = 0, j = 0;
3 let newArr = [];
4
5 while (i < arr1.length && j < arr2.length) {
6 if (arr1[i] < arr2[j]) {
7 newArr.push(arr1[i]);
8 i++;
9 } else {
10 newArr.push(arr2[j]);
11 j++;
12 }
13 }
14
15 while (i < arr1.length) {
16 newArr.push(arr1[i]);
17 i++;
18 }
19
20 while (j < arr2.length) {
21 newArr.push(arr2[j]);
22 j++;
23 }
24
25 return newArr;
26}
27
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.