482. License Key Formatting

EasyString
Leetcode Link

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:

  1. 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.

  2. We convert all lowercase letters to uppercase since the final output should be in uppercase, as specified in the rules.

  3. 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 of k, so the first group should also be k characters long.

  4. We iterate over the characters of the now dash-less and uppercase string, adding each character to a results list.

  5. 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).

  6. 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.

  7. 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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.

Which of the following method should we use to solve this 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:

  1. s = s.replace('-', '').upper(): The first line of the method removes all dashes from the input string s using replace('-', '') and converts all lowercase letters to uppercase with upper(). This simplifies the string so that we only deal with alphanumeric characters.

  2. res = []: A new list res 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.

  3. 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 by k, this remainder will determine the length of the first group; otherwise, the first group will also be k characters long. This is handled by using the logical or which returns k if len(s) % k is zero.

  4. t = 0: A variable t is initialized to keep a count of how many characters have been processed since the last dash was added to res or since the start.

  5. The code then iterates over the characters in the processed string:

    • for i, c in enumerate(s): The enumerate function is used to get both the index i and the character c during iteration.
    • res.append(c): Each character is appended to res.
    • t += 1: The counter t is incremented with each character added.

  6. The following conditional block checks if the current group is complete:

    • if t == cnt: If t equals the current group length cnt, 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 have k characters as the first group condition has been satisfied.
      • if i != len(s) - 1: A dash is appended to res only if the current character is not the last one to prevent a trailing dash.

  7. Finally, ''.join(res): The contents of the list res are combined using join 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following is a good use case for backtracking?

Example 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.

  1. First, we remove all the dashes from s and convert it to uppercase: "24A0R74K".

  2. 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 and k is 4. So, the length for the first group will be len(s) % k, which is 0. Since the remainder is 0, our first group will also be 4 characters long (equal to k).

  3. We start iterating over "24A0R74K". Initialize t to 0 for the count of characters.

  4. As we iterate, we append each character to res and increment t.

  5. After adding 4 characters ("24A0"), since t equals cnt (both are 4), we append a dash to res given that we are not at the end of the string. We reset t to 0 and set cnt to k for all following groups.

  6. We continue appending characters to res and once t again equals k, we append another dash. This process continues until all characters have been processed.

  7. 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
Not Sure What to Study? Take the 2-min Quiz：

What is the space complexity of the following code?

1int sum(int n) {
2  if (n <= 0) {
3    return 0;
4  }
5  return n + sum(n - 1);
6}

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:

  1. Removing dashes and converting the string to upper case: Both of these operations (s.replace('-', '') and s.upper()) iterate over the entire string once, which has a time complexity of O(N) where N is the length of the string s.

  2. 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 of O(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:

  1. 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 original s 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 of res would be len(s) + len(s)//k, considering an additional dash len(s)//k times. Therefore, the space complexity is O(N + N//k) which is equivalent to O(N) where N is the length of the string s.

  2. The cnt and t variables are integer counters with constant space, so they contribute O(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.

Fast Track Your Learning with Our Quick Skills Quiz:

What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?

Recommended Readings

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

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 to Algo Cheat Sheet

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 Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫